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 long long ll;
const int MAXN = 5100;
const ll MOD = 1e9 + 7;

int N;
int A, B;

ll dmod[2][MAXN];
ll dp[2][MAXN];

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> N >> A >> B;
    if (A > B) swap (A, B);

    for (int i = 1; i < A; i++)
        dmod[0][i] = 1;

    dmod[1][1] = 1;
    for (int i = 2; i <= B; i++)
    {
        dmod[1][i] = dmod[1][i-1];
        for (int j = i - (A + 1); j >= 1; j--)
            dmod[1][i] = (dmod[1][i] + dmod[1][j]) % MOD;
    }
    for (int i = 0; i < B; i++)
        dp[0][i] = dmod[1][i+1];
    ll v = dmod[1][B];
    dmod[1][B] = 0;

    for (int i = 0; i < N; i++)
    {
        for (int j = i + 1; j <= N; j++)
        {
            for (int k = 0; k < 2; k++)
            {
                dp[1-k][j] = (dp[1-k][j] + dp[k][i] * dmod[k][j-i]) % MOD;
            }
        }
    }

    dmod[1][B] = v;
    for (int i = 0; i <= N; i++)
        dp[1][N+1] = (dp[1][N+1] + dp[1][i] * dmod[1][N+1-i]) % MOD;

    /*for (int i = 0; i < N; i++)
    {
        cout << dp[0][i] << " " << dp[1][i] << "\n";
    }*/
    ll res = 1;
    for (int i = 0; i < N; i++)
        res = (res * 2) % MOD;

    if (B > 1)
        res = (res - dp[1][N+1] + 2 * MOD) % MOD;
    cout << res << "\n";
}