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 <bits/stdc++.h>

using namespace std;
#define int long long
const int MOD = 1000000007;
void add(int &a, const int &b) {
	a += b;
	if (a >= MOD) a -= MOD;
}

void sub(int &a, const int &b) {
	a -= b;
	if (a < 0) a += MOD;
}
int dp[5001][5001][2];
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, A, B;
	cin >> N >> A >> B;
	if (A > B) swap(A, B);
	//vector<vector<vector<int> > > dp(N + 1, vector<vector<int> >(N + 1, vector<int>(2, 0)));
	dp[0][0][0] = 1;
	dp[0][0][1] = 1;
	int p2[100005];
	p2[0] = 1;
	for (int i = 1; i < 100005; i++) {
		p2[i] = p2[i - 1] * 2 % MOD;
	}
	int res = 0;
	for (int j = 0; j < N; j++) {
		for (int i = j; i < N; i++) {
			// for (int x = i + 1; x <= min(N, j + B - 1); x++) {
			// 	add(dp[x][j][1], dp[i][j][0]);
			// }

			if (i == j) {
				if (i > 0) {
					add(dp[j + 1][i + 1][0], dp[j][i][0]);
				}
			} else {
				add(dp[j][i + 1][0], dp[j][i][0]);
				add(dp[j][i + 1][1], dp[j][i][1]);
			}

			{
				int mn = i + 1;
				int mx = min(N, j + B - 1) + 1;
				if (mn < mx) {
					add(dp[j][mn][1], dp[j][i][0]);
					if (mx <= N) {
						sub(dp[j][mx][1], dp[j][i][0]);
					}
				}
			}

			if (j + B <= N) {
				add(res, dp[j][i][0] * p2[N - (j + B)] % MOD);
			}
			// for (int x = i + 1; x <= min(N, i + A - 1); x++) {
			// 	//cerr << i << " " << j << " " << x << endl;
			// 	add(dp[x][x][0], dp[i][j][1]);
			// }
			{
				int mn = i + 1;
				int mx = min(N, i + A - 1) + 1;
				if (mn < mx) {
					add(dp[mn][mn][0], dp[j][i][1]);
					if (mx <= N) {
						sub(dp[mx][mx][0], dp[j][i][1]);
					}
				}
			}

			// for (int x = i + A; x <= min(N, j + B - 1); x++) {
			// 	//cerr << i << " " << j << " " << x << endl;
			// 	add(dp[x][j][0], dp[i][j][1]);
			// }

			{
				int mn = i + A;
				int mx = min(N, j + B - 1) + 1;
				if (mn < mx) {
					add(dp[j][mn][0], dp[j][i][1]);
					if (mx <= N) {
						sub(dp[j][mx][0], dp[j][i][1]);
					}
				}
			}

			{
				int x = max(i + A, j + B);
				if (x <= N) {
					add(res, dp[j][i][1] * p2[N - x] % MOD);
				}
			}
		}
	}
	cout << res << endl;
}