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 vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 1000000007LL
#define EPS 0.00001
#define f first
#define s second
#define pb push_back

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 5005
int n, a, b;
ll dp1[MN][MN][3]; //0 = run of 0s, 1 = run of 1s. 2 = run of 1s and just came from 0-jump
//legal moves:
//0->0, 0->1, 1->0, 1->1, 1->2 via 0-jump, 2->1, 2->2. (can't have two 0-jumps in a row)
ll modExp(ll b, ll ex){
    ll prod = 1;
    while(ex > 0){
        if(ex % 2 == 0){
            b = (b * b) % MOD;
            ex /= 2;
        } else{
            prod = (prod*b) % MOD;
            ex--;
        }
    }
    
    return prod;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> a >> b;
    if(a > b) swap(a, b);
    dp1[1][1][0] = dp1[1][1][1] = 1;
    dp1[a][a][2] = 1;
    FOR(i, 1, n-1){
        FOR(j, 1, a-1){
            //cout << i << " " << j << " 0 " << dp1[i][j][0] << "\n";
            dp1[i+1][j+1][0] = (dp1[i+1][j+1][0]+dp1[i][j][0])%MOD;
            dp1[i+1][1][1] = (dp1[i+1][1][1]+dp1[i+1][j+1][0])%MOD;
        }
        FOR(j, 1, b-1){
            //cout << i << " " << j << " 1 " << dp1[i][j][1] << "\n";
            dp1[i+1][j+1][1] = (dp1[i+1][j+1][1]+dp1[i][j][1])%MOD;
            dp1[i+1][1][0] = (dp1[i+1][1][0]+dp1[i][j][1])%MOD;
            if(i+a<=n && j+a<b) dp1[i+a][j+a][2] = (dp1[i+a][j+a][2]+dp1[i][j][1])%MOD;
            //CHECK IF BOUND OBO
        }
        FOR(j, 1, b-1){ //state 2
            //cout << i << " " << j << " 2 " << dp1[i][j][2] << "\n";
            dp1[i+1][j+1][2] = (dp1[i+1][j+1][2]+dp1[i][j][2])%MOD;
            dp1[i+1][j+1][1] = (dp1[i+1][j+1][1]+dp1[i][j][2])%MOD;
        }
    }
    ll ans = 0;
    FOR(i, 1, a-1){
        //cout << n << " " << i << " 0 " << dp1[n][i][0] << "\n";
        ans = (ans+dp1[n][i][0])%MOD;
    }
    FOR(i, 1, b-1){
        //cout << n << " " << i << " 1 " << dp1[n][i][1] << "\n";
        //cout << n << " " << i << " 2 " << dp1[n][i][2] << "\n";
        ans = (ans+dp1[n][i][1])%MOD;
        ans = (ans+dp1[n][i][2])%MOD;
    }
    ll fin = modExp(2, n)-ans;
    fin = (fin+MOD)%MOD;
    cout << fin << "\n";

    return 0;
}
