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 pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define FOR(i,a,b) for (int i=a;i<=b;++i)
#define FORD(i,a,b) for (int i=a;i>=b;--i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
typedef vector<int> vec;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
const int MO=1e9+7;
int n,A,B;
LL f[5555][2][2],g[5555][2],ANS,ans;
int main(){
	cin>>n>>A>>B;
	if (A>B) swap(A,B);
	FOR(i,1,B-1){
		f[i][0][0]=(i>=A);
		FOR(j,A,i-1) (f[i][0][0]+=f[i-j][0][1])%=MO;
		f[i][0][1]=0;
		FOR(j,1,i-1) (f[i][0][1]+=f[i-j][0][0])%=MO;
		f[i][1][0]=0;
		FOR(j,A,i-1) (f[i][1][0]+=f[i-j][1][1])%=MO;
		f[i][1][1]=1;
		FOR(j,1,i-1) (f[i][1][1]+=f[i-j][1][0])%=MO;
	}
	FOR(i,1,n){
		g[i][0]=(f[i][0][1]+f[i][1][1])%MO;
		FOR(j,1,min(B-1,i-1)) (g[i][0]+=g[i-j][1]*f[j][1][1])%=MO;
		g[i][1]=(i<A);
		FOR(j,1,min(A-1,i-1)) (g[i][1]+=g[i-j][0])%=MO;
	}
	ans=(f[n][0][0]+f[n][0][1]+f[n][1][0]+f[n][1][1])%MO;
	FOR(i,1,n-1) (ans+=g[i][1]*(f[n-i][1][0]+f[n-i][1][1]))%=MO;
	(ans+=g[n][1])%=MO;
	ANS=1;
	FOR(i,1,n) ANS=ANS*2%MO;
	(ANS-=ans)%=MO;
	ANS=(ANS%MO+MO)%MO;
	cout<<ANS<<endl;
	return 0;
}