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 ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 5005, MOD = 1e9 + 7;
int dp[N][N][2], dp_add[N][N], dp_add_d[N][N];

void add(int &a, int b) {
    a += b;
    if (a >= MOD)
        a -= MOD;
    if (a < 0)
        a += MOD;
}

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

    int n, a, b;
    cin >> n >> a >> b;

    if (a < b)
        swap(a, b);

    dp[0][0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= n; j++) {
            if (i >= j && i >= a) {
                add(dp_add[i + 1][j], dp[i][j][0]);
            }
            else {
                add(dp_add[i + b][j], dp[i][j][0]);

                int lim = min(b - 1, n - i - a);

                if (lim > 0) {
                    add(dp_add_d[i + 1][i + 1 + a], dp[i][j][0]);
                    add(dp_add_d[i + lim + 1][i + 1 + lim + a], -dp[i][j][0]);
                }
            }
        }

        for (int j = 0; j <= n; j++) {
            add(dp_add[i + 1][j], dp_add[i][j]);
            add(dp[i + 1][j][1], dp_add[i + 1][j]);

            add(dp_add_d[i + 1][j + 1], dp_add_d[i][j]);
            add(dp[i + 1][j + 1][1], dp_add_d[i + 1][j + 1]);

            for (int k = 0; k < 2; k++) {
                add(dp[i + 1][j][0], dp[i][j][k]);
            }
        }
    }

    int ans = 0;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j < 2; j++) {
            add(ans, dp[n][i][j]);
        }
    }

    cout << ans;

	return 0;
}