Snuke has a string x of length N. Initially, every character in x is `0`.

Snuke can do the following two operations any number of times in any order:

* Choose A consecutive characters in x and replace each of them with `0`.
* Choose B consecutive characters in x and replace each of them with `1`.



Find the number of different strings that x can be after Snuke finishes doing operations. This count can be enormous, so compute it modulo (10^9+7).

Constraints

* 1 \leq N \leq 5000
* 1 \leq A,B \leq N
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N A B


Output

Print the number of different strings that x can be after Snuke finishes doing operations, modulo (10^9+7).

Examples

Input

4 2 3


Output

11


Input

10 7 2


Output

533


Input

1000 100 10


Output

828178524
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int mod = 1000000007;
int n, a, b;
int dp1[5001][2];	//dp1[len][nowChar] : 1個以上の1, A個以上の0を交互に配置(1スタート)
int dp2[5001][2];	//dp2[len][nowChar] : nowChar = 0 : A個未満0, 1 : __(dp1を利用)

signed main() {
	int i, j, k;
	
	cin >> n >> a >> b;
	if (a > b) swap(a, b);
	
	dp1[0][1] = 1;
	for (i = 0; i < b; i++) {
		//dp1[i][0] -> dp1[i + a以上][1]
		for (j = i + a; j < b; j++) {
			dp1[j][1] += dp1[i][0];
			dp1[j][1] %= mod;
		}
		//dp1[i][1] -> dp1[i + 1以上][0]
		for (j = i + 1; j < b; j++) {
			dp1[j][0] += dp1[i][1];
			dp1[j][0] %= mod;
		}
	}
	
	dp2[0][0] = 1;
	dp2[0][1] = 1;
	for (i = 0; i < n; i++) {
		//dp2[i][0] -> dp2[i + a未満][1]
		for (j = i + 1; j < i + a && j <= n; j++) {
			dp2[j][1] += dp2[i][0];
			dp2[j][1] %= mod;
		}
		//dp2[i][1] -> dp2[i + b未満][0]
		for (j = i + 1; j < i + b && j <= n; j++) {
			dp2[j][0] += dp2[i][1] * dp1[j - i][0] % mod;
			dp2[j][0] %= mod;
			if (i == 0 || j == n) {
				dp2[j][0] += dp2[i][1] * dp1[j - i][1] % mod;
				dp2[j][0] %= mod;
			}
		}
	}
	
	//余事象の個数はdp2[n][0] + dp2[n][1];
	int ng = (dp2[n][0] + dp2[n][1]) % mod;

	//全体2^N個から引けば答え
	int p2 = 1;
	for (i = 0; i < n; i++) { p2 *= 2; p2 %= mod; }
	
	cout << (p2 + mod - ng) % mod << endl;
	return 0;
}