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>

constexpr auto MOD = (long long)1e9+7;
constexpr auto MAXN = 6000;

long long Pow(long long a,long long b){
    long long ans = 1LL;
    for(;b;b>>=1,(a*=a)%=MOD)
        if(b&1) (ans *= a) %= MOD;
    return ans;
}

long long f[4][MAXN];
long long g[MAXN][2];

signed main(void)
{
    int len,a,b;
    long long ans=0;

    std::cin>>len>>a>>b;
    if(a > b) std::swap(a,b);
    if(b<2) goto OP;

    f[0][1] = 1LL;
    for(int i=2;i<b;++i){
        f[0][i] = 1;
        for(int j=1;j<i;++j) (f[0][i] += f[1][i-j]) %= MOD;
        for(int j=i-a;j>=0;--j) (f[1][i] += f[0][j]) %= MOD;

        for(int j=1;j<i;++j) (f[2][i] += f[3][j]) %= MOD;
        if(i >= a) f[3][i] = 1;
        for(int j=i-a;j>=0;--j) (f[3][i] += f[2][j]) %= MOD;
    }
    for(int i=1;i<=len;++i){
        if(i < b) g[i][1] = f[0][i] + f[2][i];
        for(int j=1; j<b&&i-j>0; ++j)
            (g[i][1] += g[i-j][0]*f[0][j]) %= MOD;

        if(i < a) g[i][0] = 1LL;
        for(int j=1; j<a&&i-j>0; ++j)
            (g[i][0] += g[i-j][1]) %= MOD;
    }

    ans = (g[len][0]+g[len][1]) % MOD;
    for(int i=1;i<len;++i) (ans += g[i][0]*f[1][len-i]) %= MOD;
    
 OP:
    std::cout<< (Pow(2LL,len)-ans+MOD)%MOD <<std::endl;
    
    return 0;
}
