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;

#define all(x) (x).begin(), (x).end()

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;

const int N = 5200;
const int MOD = 1e9 + 7;

int dp[N][2];
int dp1[N][2];

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    if (a > b) swap(a, b);
    dp1[0][0] = 1;
    for (int i = 1; i < b; i++)
    {
        for (int j = a; j <= i; j++)
        {
            dp1[i][0] = (dp1[i][0] + dp1[i - j][1]) % MOD;
        }
        dp1[i][1] = (dp1[i - 1][0] + dp1[i - 1][1]) % MOD;
    }

    dp[0][1] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < a && j <= i; j++)
        {
            dp[i][0] = (dp[i][0] + dp[i - j][1]) % MOD;
        }
        for (int j = 1; j < b && j <= i; j++)
        {
            dp[i][1] = (dp[i][1] + 1ll * dp[i - j][0] * dp1[j][1]) % MOD;
        }
        //cout << i << " " << dp[i][0] << " " << dp[i][1] << "\n";
    }
    int ans = 1;
    for (int i = 0; i < n; i++) ans = (ans + ans) % MOD;

    for (int p = 0; p < b; p++)
    {
        for (int s = 0; s < b && s + p < n; s++)
        {
            ans = (ans - 1ll * (dp1[p][1] + dp1[p][0]) * (dp1[s][1] + dp1[s][0]) % MOD * dp[n - p - s][0]) % MOD;
            ans = (ans + MOD) % MOD;
        }
    }

    cout << ans;
}

/*

*/
