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;
const int N=5005,mod=1e9+7;
int n,a,b;
ll f[N],c[N][N],dp[N][2];
ll C(int n,int m)
{
    if(m==0||n==m) return 1;
    if(m==1) return n;
    if(c[n][m]) return c[n][m];
    return c[n][m]=(C(n-1,m-1)+C(n-1,m))%mod;
}
ll qpow(ll a,ll n)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)if(n&1) ans=ans*a%mod;
    return ans;
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    if(a>b) swap(a,b);
    f[1]=1;
    for(int i=1;i<b;i++)
    {
        f[i+1]=(f[i+1]+f[i])%mod;
        for(int j=a;i+j+1<=b;j++)
                f[i+j+1]=(f[i+j+1]+f[i])%mod;
    }
    dp[0][0]=dp[0][1]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<i+a&&j<=n;j++)
            (dp[j][0]+=dp[i][1])%=mod;
        for(int j=i+1;j<i+b&&j<=n;j++)
            (dp[j][1]+=dp[i][0]*f[j-i+(i==0||j==n)])%=mod;
    }
    ll ans=qpow(2,n);
    ans=(ans-dp[n][0]-dp[n][1])%mod;
    ans=(ans+mod)%mod;
    printf("%lld\n",ans);
}
