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 <numeric>
#include <iostream>
using namespace std;

int M = 1000000007;
long long dp[5001][3][5001];

int main() {
    int n, a, b; cin >> n >> a >> b;
    if (a > b) swap(a, b);

    long long ans = 1;
    for (int i = 0; i < n; i++) ans = ans * 2 % M;
    if (a > 1) {
        dp[0][0][1] = 1;
        dp[0][1][1] = 0;
        dp[0][2][1] = 1;
        for (int i = 1; i < n; i++) {
            dp[i][0][1] = accumulate(dp[i-1][2]+1, dp[i-1][2]+b, 0LL) % M;
            for (int j = 2; j < a; j++) dp[i][0][j] = dp[i-1][0][j-1];
            if (i+1 == a) dp[i][1][a] = 1;
            for (int j = a+1; j < b; j++)
                dp[i][1][j] = (dp[i-1][1][j-1] + (i >= a ? dp[i-a][2][j-a] : 0)) % M;
            dp[i][2][1] = accumulate(dp[i-1][0]+1, dp[i-1][0]+a, 0LL) % M;
            for (int j = 2; j < b; j++)
                dp[i][2][j] = (dp[i-1][1][j-1] + dp[i-1][2][j-1]) % M;
        }
        ans -= accumulate(dp[n-1][0]+1, dp[n-1][0]+a, 0LL) % M;
        ans -= accumulate(dp[n-1][1]+1, dp[n-1][1]+b, 0LL) % M;
        ans -= accumulate(dp[n-1][2]+1, dp[n-1][2]+b, 0LL) % M;
    }
    cout << (ans % M + M) % M << endl;
}
