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 <iostream>

using namespace std;
typedef long long ll;
constexpr ll mod = 1000000007;
ll f[5010][2] = {},g[5010][2] = {},dp[5010][2] = {};
int main(){
    int i,j,n,a,b;
    cin >> n >> a >> b;
    if(a<b) swap(a,b);
    for(i=0;i<b;i++) f[i][0] = 1;
    for(i=b;i<=n;i++){
        f[i][0] += (f[i - 1][0] + f[i - 1][1])%mod;
        for(j=i - b;j>=0;j--){
            (f[i][1] += f[j][0]) %= mod;
        }
    }
    for(i=0;i<=n;i++){
        for(j=max(a,i - b + 1);j<=i - 1;j++) (g[i][1] += f[j - 1][0]) %= mod;
        for(j=max(1,i - b + 1);j<=min(i - 1,a - 1);j++) (g[i][0] += f[j - 1][0]) %= mod;
    }
    dp[0][0] = 1;
    for(i=1;i<=n;i++){
        for(j=i - 1;j>=1;j--){
            (dp[i][1] += (g[i - j][1]*dp[j][0] + (g[i - j][1] + g[i - j][0])*dp[j][1])%mod) %= mod;
            (dp[i][0] += (g[i - j][0]*dp[j][0])%mod) %= mod;
        }
        for(j=1;j<b;j++){
            if(j<=i && i - j>=a) (dp[i][1] += f[i - j][0]) %= mod;
            if(j<=i && i - j<a) (dp[i][0] += f[i - j][0]) %= mod;
        }
    }
    ll ans = 0;
    (ans += dp[n][1] + f[n][0] + f[n][1]) %= mod;
    for(i=1;i<n;i++){
        (ans += (f[n - i - 1][0] + f[n - i - 1][1])*dp[i][1]%mod) %= mod;
        if(n - i>=a) (ans += (f[n - i - 1][0] + f[n - i - 1][1])*dp[i][0]%mod) %= mod;
    }
    cout << ans << endl;
}