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;
const int N=10010,mod=1e9+7;
int n,a,b,f[N],g[N],h[N],hh[N],ans;
int power(int x,int y){
    int z=1;
    for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
    return z;
}
int main(){
    scanf("%d%d%d",&n,&a,&b);
    if(a>b)swap(a,b);g[a]=g[0]=1;
    for(int i=a+1;i<=b-2;i++){
        g[i]=g[i-1];
        for(int j=i-a-1;~j;j--)(g[i]+=g[j])%=mod;
    }
    f[0]=g[0]=1;for(int i=1;i<=b-2;i++)(g[i]+=g[i-1])%=mod;
    for(int i=1;i<a;i++)
        for(int j=0;j<b;j++)
            j?(h[i+j]+=j>1?g[j-2]:1)%=mod:0,
            (hh[i+j]+=j?g[j-1]:1)%=mod;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            f[i]=(f[i]+1ll*f[i-j]*(i-j?h[j]:hh[j]))%mod;
    for(int i=n;i>n-b;i--)ans=(ans+1ll*f[i]*(i<n?g[n-i-1]:1))%mod;
    cout<<((power(2,n)-ans)%mod+mod)%mod;
    return 0;
}