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;
typedef long long ll;
typedef long double ld;

const int MAX=5005,mod=1e9+7,inf=0x3f3f3f3f;

typedef pair < ll, ll > ii;
int f[MAX][MAX][2],F[MAX][MAX][2],cnt[MAX];
#define X first
#define Y second
#define pb push_back
//vector < int > pr[MAX];
int n,m;
//ll a[MAX];
int A,B;
int get(int a,int b){
    a+=b;if(a>=mod) a-=mod;return a;
}
int main()
{
    //memset(ST,0,sizeof ST);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("45C.inp","r",stdin);freopen("45C.out","w",stdout);
    cin>>n;
    cin>>A>>B;
    //cout<<mod*2;
    if(A>B) swap(A,B);
    ll ans=1;
    f[0][0][1]=1;
    f[0][0][0]=1;
    cnt[0]=1;
    F[0][0][0]=1;
    F[0][0][1]=1;
    for(int i=1;i<=n;i++){ans=ans<<1;if(ans>=mod) ans-=mod;}
    for(int i=1;i<=n;i++){
        if(i>=A) f[i][0][0]=(cnt[i-1]-cnt[i-A]+mod)%mod;
        else f[i][0][0]=cnt[i-1];
        F[i][i][0]=get( F[i-1][i][0],f[i][0][0] );
        for(int j=1,ma=min(B-1,i);j<=ma;j++){
            //for(int u=A;u<j;u++) f[i][j][0]+=f[i-u][j-u][1];
            if(i>=A) f[i][j][0]=F[i-A][i-j][1];

            F[i][i-j][0]=get( F[i-1][i-j][0],f[i][j][0] );
        }
        for(int j=1,ma=min(B-1,i);j<=ma;j++){
            //for(int u=1;u<=j;u++) f[i][j][1]+=f[i-u][j-u][0];

            f[i][j][1]=F[i-1][i-j][0];

            F[i][i-j][1]=get(F[i-1][i-j][1],f[i][j][1]);
            cnt[i]=get(f[i][j][1],cnt[i]);
        }
        cnt[i]=get(cnt[i-1],cnt[i]);
    }
    ll temp=0;
    for(int j=0;j<B;j++){
        temp=(temp+f[n][j][1]+f[n][j][0])%mod;
        //cout<<j<<' '<<f[n][j][1]<<' '<<f[n][j][0]<<'\n';
    }
    cout<<(ans-temp+mod)%mod;
}
