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 = 5010;
const int mod = 1e9+7;

int n, A, B;
int f[maxn][2], g[maxn][2], a[maxn][maxn], h[maxn];

int calh(int l, int a, int b) {
	if (!a && !b) return h[l];
	if (l == 1) return 1;
	return h[l - a - b];
}

int main() {
	scanf("%d%d%d", &n, &A, &B);
	if (A > B) swap(A, B);
	f[0][0] = g[0][0] = 1;
	a[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			if (!j || j >= A) a[i][0] = (a[i][0] + a[i-1][j]) % mod;
			a[i][j+1] = (a[i][j+1] + a[i-1][j]) % mod;
		}
	}
	for (int i = 0; i <= n; i++) {
		h[i] = (h[i] + a[i][0]) % mod;
		for (int j = A; j <= i; j++) {
			h[i] = (h[i] + a[i][j]) % mod;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int k = 1; k < A; k++) {
			f[i][0] = (f[i][0] + g[i-k][0]) % mod;
			f[i][1] = (f[i][1] + g[i-k][1]) % mod;
		}
		for (int k = 1; k < B && k <= i; k++) {
			g[i][0] = (g[i][0] + 1LL * f[i-k][0] * calh(k, k < i, i != n) % mod) % mod;
		}
		for (int k = 1; k <= i; k++) {
			g[i][1] = (g[i][1] + 1LL * f[i-k][1] * calh(k, k < i, i != n) % mod) % mod;
		}
		for (int k = B; k <= i; k++) {
			g[i][1] = (g[i][1] + 1LL * f[i-k][0] * calh(k, k < i, i != n) % mod) % mod;
		}
	}
	int ans = (f[n][1] + g[n][1]) % mod;
	printf("%d\n", ans);
	return 0;
}