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 rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
typedef long long LL;
const int N=5005,P=1e9+7;
int n,A,B,f[N],g[N][2];
int fpow(int k1,int k2){
	int k3=1;
	for(;k2;k2>>=1,k1=1LL*k1*k1%P)if(k2&1)k3=1LL*k3*k1%P;
	return k3;
}
int main(){
	cin>>n>>A>>B;
	if(A>B)swap(A,B);
	f[1]=1;
	rep(i,1,B-1){
		(f[i+1]+=f[i])%=P;
		rep(j,i+A+1,B)(f[j]+=f[i])%=P;
	}
//	printf(">>> %d %d\n",A,B);
//	rep(i,1,B)printf("%d ",f[i]);puts("");
	rep(i,1,B-1)g[i][0]=f[i+1];
	rep(i,1,A-1)g[i][1]=1;
	rep(i,1,n){
		rep(j,i+1,min(n,i+B-1))if(j==n)(g[j][0]+=1LL*g[i][1]*f[j-i+1]%P)%=P;else (g[j][0]+=1LL*g[i][1]*f[j-i]%P)%=P;
		rep(j,i+1,min(n,i+A-1))(g[j][1]+=g[i][0])%=P;
//		printf("g[%d][0]=%d g[%d][1]=%d\n",i,g[i][0],i,g[i][1]);
	}
	printf("%lld\n",((LL)fpow(2,n)-g[n][0]-g[n][1]+P+P)%P);
	return 0;
}