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 MX = 5005, md = 1000000007;

void calc(int h[MX], int b, int a, int n) {
	static int dp[MX][MX], add[MX][MX], zero[MX];
	
	memset(dp, 0, sizeof dp);
	memset(add, 0, sizeof add);
	memset(zero, 0, sizeof zero);
	
	for (int i = 1; i < b; i++) {
		dp[i][0] = 1;
	}
	
	for (int i = 0; i <= n; i++) {
		dp[i][0] += zero[i];
		
		zero[i + 1] += zero[i];
		zero[i + 1] %= md;
		
		for (int j = 0; j < a; j++) {
			dp[i][j] += add[i][j];
			dp[i][j] %= md;
			
			if (j + 1 == a) continue;
			
			add[i + 1][j + 1] += add[i][j];
			add[i + 1][j + 1] %= md;
			
			if (i + 1 + b <= n) {
				add[i + 1 + b][j + 1 + b] += dp[i][j];
				add[i + 1 + b][j + 1 + b] %= md;
			}
			
			dp[i + 1][j + 1] += dp[i][j];
			dp[i + 1][j + 1] %= md;
			
			zero[i + 2] += dp[i][j];
			zero[i + 2] %= md;
			
			if (i + 1 + b <= n) {
				zero[i + 1 + b] += md - dp[i][j];
				zero[i + 1 + b] %= md;
			}
		}
	}
	
	for (int i = 0; i <= n; i++) {
		h[i] = 0;
		for (int j = 0; j < a; j++) {
			h[i] += dp[i][j];
			h[i] %= md;
		}
	}
}

int f[MX], g[MX], h[MX];

int main() {
	int n, a, b;
	ignore = scanf("%d %d %d", &n, &a, &b);
	
	if (a < b) swap(a, b);
	
	f[0] = 1;
	for (int i = b; i <= n; i++) f[i] = 1;
	
	for (int i = 0; i < n; i++) {
		f[i + 1] += f[i];
		f[i + 1] %= md;
		
		for (int j = b; i + 1 + j <= n; j++) {
			f[i + 1 + j] += f[i];
			f[i + 1 + j] %= md;
		}
	}
	
	calc(g, b, a, n);
	calc(h, b, n + 1, n);
	
	int ans = f[n];
	
	// prefix
	for (int len = a - 1; len < n; len++) {
		ans = (ans + f[len] * 1LL * g[n - 1 - len]) % md;
	}
	
	// suffix
	for (int len = a - 1; len < n; len++) {
		ans = (ans + f[len] * 1LL * h[n - 1 - len]) % md;
	}
	
	// middle
	for (int len = a - 2; len + 2 <= n; len++)
		for (int L = 0; L + len + 2 <= n; L++) {
			ans = (ans + f[len] * 1LL * h[L] % md * g[n - L - len - 2]) % md;
		}
	
	printf("%d\n", ans);
	
	return 0;
}
