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"

#define sz(x) (int)x.size()
#define ld long double
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

const ll INF = 2e18;
const ll MOD = 1e9 + 7;

ll n, a, b, res = 0;
vector<ll> p2, g;
vector<vector<ll>> dp1, dp2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> a >> b;
    p2.assign(n + 1, 1);
    for(int i = 0; i < n; ++i){
        p2[i + 1] = p2[i] * 2;
        p2[i + 1] %= MOD;
    }
    if(a > b) swap(a, b);
    if(b == 1){
        cout << p2[n];
        return 0;
    }
    dp1.assign(n + 1, vector<ll>(2, 0));
    dp2.assign(n + 1, vector<ll>(2, 0));
    dp1[0][0] = dp1[0][1] = 1;
    for(int i = 1; i <= n; ++i){
        for(int k = 0; k < 2; ++k){
            for(int j = 1; j <= i; ++j){
                if(!k && j < a) continue;
                dp1[i][k] += dp1[i - j][k ^ 1];
                dp1[i][k] %= MOD;
            }
        }
    }
    g.assign(n + 1, 0);
    g[0] = 1;
    for(int i = 1; i <= n; ++i){
        g[i] = dp1[i][0] + dp1[i][1];
        g[i] %= MOD;
    }
    for(ll i = 1; i < n; ++i){
        if(i < a) dp2[i][0]++;
        for(ll j = 0; j < min(i, a); ++j){
            dp2[i][0] += dp2[i - j][1];
            dp2[i][0] %= MOD;
        }
        if(i < b){
            dp2[i][1] += g[i - 1];
            dp2[i][1] %= MOD;
        }
        for(ll j = 1; j < min(i, b); ++j){
            ll w = j == 1 ? 1 : g[j - 2];
            dp2[i][1] += dp2[i - j][0] * w;
            dp2[i][1] %= MOD;
        }
        if(n - i < b){
            res += dp2[i][0] * g[n - i - 1];
            res %= MOD;
        }
        if(n - i < a){
            res += dp2[i][1];
            res %= MOD;
        }
    }
    cout << ((p2[n] - res)%MOD + MOD)%MOD;
    return 0;
}