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>
typedef long long LL;
using namespace std;
const int N=5005,mod=1e9+7;
int n,A,B,f[N][N][2],sum1[N][N][2],sum2[N][N][2],ans;
//sum1[i][j][o] = sigma f[i][s][o] (s<=j)
//sum2[i][j][o] = sigma f[i+s][s][o] (s<=j)
int qpow(int x,int y) {
	int res=1;
	while(y) {
		if(y&1) res=(LL)res*x%mod;
		x=(LL)x*x%mod, y>>=1;
	}
	return res;
}
int main() {
	scanf("%d%d%d",&n,&A,&B);
	if(A>B) swap(A,B);
	f[0][0][0]=1, f[0][0][1]=1;
	for(int i=0;i<=n;++i) {
		if(i) {
			for(int j=1;j <= i && j < B;++j) {
				if(j < A) f[i][j][0]=sum1[i-j][i-j][1];
				if(j >= A) f[i][j][0]=sum2[i-j][j-A][1];
				f[i][j][1]=sum1[i-j][min(A-1,i-j)][0];
				if(j >= A)
					f[i][j][1]=((LL)f[i][j][1]+sum2[i-j][j-1][0]+mod-sum2[i-j][A-1][0])%mod;
			}
		}
		for(int j=0;j<=i;++j) for(int o=0;o<2;++o) {
			sum1[i][j][o]=(sum1[i][j-1][o]+f[i][j][o])%mod;
			sum2[i-j][j][o]=(sum2[i-j][j-1][o]+f[i][j][o])%mod;
		}
	}
	for(int i=1;i<=n;++i) ans=(ans+f[n][i][0])%mod, ans=(ans+f[n][i][1])%mod;
	ans=(qpow(2,n)+mod-ans)%mod;
	printf("%d",ans);
	return 0;
}