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>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;

const int MOD = (int) 1e9 + 7;

int dp[5005][5005][5], dps[5005][5];
int answer[5005][5], step[5005];

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
 	ios_base::sync_with_stdio(0); cin.tie(0);
 	int n, A, B;
 	cin >> n >> A >> B;
 	if (A > B) swap(A, B);

 	step[0] = 1;
 	for (int i = 1; i <= n; i++) step[i] = 2 * step[i - 1] % MOD;
 	if (A == 1) cout << step[n] << '\n', exit(0);

 	dp[1][1][0] = 1, dp[1][1][3] = 1;
 	for (int i = 1; i < B; i++)
 		for (int j = 1; j <= i; j++)
 		{
 		 	dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][0]) % MOD;
 		 	if (j >= A) dp[i + 1][1][1] = (dp[i + 1][1][1] + dp[i][j][0]) % MOD;
 		 	dp[i + 1][1][0] = (dp[i + 1][1][0] + dp[i][j][1]) % MOD;
 		 	dp[i + 1][j + 1][1] = (dp[i + 1][j + 1][1] + dp[i][j][1]) % MOD;
 		 	dp[i + 1][j + 1][2] = (dp[i + 1][j + 1][2] + dp[i][j][2]) % MOD;
 		 	if (j >= A) dp[i + 1][1][3] = (dp[i + 1][1][3] + dp[i][j][2]) % MOD;
 		 	dp[i + 1][1][2] = (dp[i + 1][1][2] + dp[i][j][3]) % MOD;
 		 	dp[i + 1][j + 1][3] = (dp[i + 1][j + 1][3] + dp[i][j][3]) % MOD;
 		}
 	for (int i = 1; i < B; i++)
 		for (int j = 1; j <= i; j++)
 		{
 		 	if (j >= A) answer[i][0] = (answer[i][0] + dp[i][j][0]) % MOD;
 		 	answer[i][1] = (answer[i][1] + dp[i][j][1]) % MOD;
 		 	if (j >= A) answer[i][2] = (answer[i][2] + dp[i][j][2]) % MOD;
 		 	answer[i][3] = (answer[i][3] + dp[i][j][3]) % MOD;
 		}

 	for (int i = 1; i < A; i++) dps[i][0] = 1;
 	for (int i = 1; i < B; i++) dps[i][1] = (answer[i][1] + answer[i][3]) % MOD;

 	for (int i = 1; i <= n; i++)
 	{
 	 	for (int j = 1; j < min(B, n - i + 1); j++)
 	 	{
 	 	 	int c = answer[j][3];
 	 	 	if (j == n - i) c = (c + answer[j][2]) % MOD;
 	 	 	dps[i + j][1] = ((ll) dps[i + j][1] + (ll) dps[i][0] * (ll) c) % (ll) MOD;
 	 	}
 	 	for (int j = 1; j < min(A, n - i + 1); j++)
 	 		dps[i + j][0] = (dps[i + j][0] + dps[i][1]) % MOD;
 	}
 	int ans = ((ll) step[n] - (ll) dps[n][0] - (ll) dps[n][1] + (ll) 2 * MOD) % (ll) MOD;
 	cout << ans << '\n';
 	return 0;
}