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 <cstdio>
#include <algorithm>

using namespace std;

const int mod = 1000000007;
int dp[5001];
int dp2[5001];
int dp3[5001][2];

int main() {
    int n, a, b, ans, i, j, k;
    
    scanf("%d %d %d", &n, &a, &b);
    
    if (a > b) swap(a, b);
    
    dp[1] = 1;
    
    for (i = 1; i < n; i++) {
        dp[i + 1] += dp[i];
        if (dp[i + 1] >= mod) dp[i + 1] -= mod;
        
        for (j = a + 1; i + j <= n; j++) {
            dp[i + j] += dp[i];
            if (dp[i + j] >= mod) dp[i + j] -= mod;
        }
    }
    
    dp2[0] = 1;
    
    for (i = 0; i < n; i++) {
        dp2[i + 1] += dp2[i];
        if (dp2[i + 1] >= mod) dp2[i + 1] -= mod;
        
        for (j = a + 1; i + j <= n; j++) {
            dp2[i + j] += dp2[i];
            if (dp2[i + j] >= mod) dp2[i + j] -= mod;
        }
    }
    
    for (i = 0; i < b; i++) dp3[i][1] = dp2[i];
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < 2; j++) {
            if (dp3[i][j] == 0) continue;
            
            if (j != 0) {
                for (k = 1; k < a && i + k <= n; k++) {
                    dp3[i + k][0] += dp3[i][j];
                    if (dp3[i + k][0] >= mod) dp3[i + k][0] -= mod;
                }
            }
            
            if (j != 1) {
                for (k = 1; k < b && i + k < n; k++) {
                    dp3[i + k][1] += (long long)dp3[i][j] * dp[k] % mod;
                    if (dp3[i + k][1] >= mod) dp3[i + k][1] -= mod;
                }
                
                if (n - i < b) {
                    dp3[n][1] += (long long)dp3[i][j] * dp2[n - i] % mod;
                    if (dp3[n][1] >= mod) dp3[n][1] -= mod;
                }
            }
        }
    }
    
    ans = 1;
    for (i = 0; i < n; i++) ans = ans * 2 % mod;
    
    for (i = 0; i < 2; i++) {
        ans -= dp3[n][i];
        if (ans < 0) ans += mod;
    }
    
    printf("%d\n", ans);
    
    return 0;
}
