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;
const int MAXN = 5005;
const int P = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, a, b, dp[MAXN][MAXN], two[MAXN];
int pd[MAXN][MAXN], aux[MAXN];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int main() {
	read(n), read(a), read(b);
	if (a < b) swap(a, b); two[0] = 1;
	for (int i = 1; i <= n; i++)
		two[i] = 2ll * two[i - 1] % P;
	dp[0][0] = 1;
	for (int i = 0; i <= n; i++) {
		if (i != 0) update(aux[i], aux[i - 1]);
		update(dp[i][1], aux[i]);
		for (int j = 1; j <= a; j++) {
			update(dp[i][j], pd[i][j]);
			update(pd[i + 1][min(j + 1, a)], pd[i][j]);
		}
		if (i == n) break;
		for (int j = 0; j <= a - 1; j++) {
			update(dp[i + 1][j + 1], dp[i][j]);
			
			update(aux[i + 2], dp[i][j]);
			if (i + b + 1 <= n) update(aux[i + b + 1], P - dp[i][j]);
			
			if (i + b + 1 <= n) update(pd[i + b + 1][min(j + b + 1, a)], dp[i][j]);
			
			if (n - i >= b) update(dp[n][min(j + n - i, a)], dp[i][j]);
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++)
		update(ans, 1ll * dp[i][a] * two[n - i] % P);
	cout << ans << endl;
	return 0;
}
