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;

const int maxn = 5010, P = 1000000007;
int n, A, B, ans, pw[maxn], f[maxn][maxn][2], pre[maxn][maxn][2], h[maxn];

int main() {
    scanf("%d %d %d", &n, &A, &B);
    if (A < B) swap(A, B);
    pw[0] = pw[1] = 1;
    for (int i = 2; i <= n; i++) {
        pw[i] = (pw[i - 1] + pw[i - 1]) % P;
    }
    f[0][0][0] = f[0][0][1] = 1, h[0] = 1;
    pre[0][0][0] = pre[0][0][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            (f[i][j][0] += pre[i - 1][i - j][1]) %= P;
            if (i >= B) (f[i][j][1] += pre[i - B][i - j][0]) %= P;
        }
        for (int j = max(0, i - B + 1); j < i; j++) {
            (f[i][0][1] += h[j]) %= P;
        }
        for (int j = A; j <= i; j++) {
            int s = 1LL * (f[i][j][0] + f[i][j][1]) * pw[n - i] % P;
            (ans += s) %= P, f[i][j][0] = f[i][j][1] = 0;
        }
        for (int j = 0; j <= i; j++) {
            (h[i] += f[i][j][0]) %= P;
            pre[i][i - j][0] = (pre[i - 1][i - j][0] + f[i][j][0]) % P;
            pre[i][i - j][1] = (pre[i - 1][i - j][1] + f[i][j][1]) % P;
        }
    }
    printf("%d\n", (ans + P) % P);
    return 0;
}