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;
typedef long long ll;
const int mod = 1e9+7;
int dp0[5005][5005], dp1[5005][5005], dp2[5005][5005], sum1[5005][5005];
int main(){
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    if(a > b) swap(a, b);
    dp1[0][0] = 1;
    for(int j=0;j<=n;j++) sum1[0][j] = 1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=a-1;j++) if(i-j >= 0) dp0[i][0] = (dp0[i][0] + sum1[i-j][n])%mod;
        if(i >= a) for(int j=0;j<=b-a-1;j++) dp2[i][j+a] = (dp2[i][j+a] + dp1[i-a][j])%mod;

        for(int j=0;j<b-1;j++){
            dp2[i][j+1] = (dp2[i][j+1] + dp2[i-1][j])%mod;
        }
        for(int j=0;j<b-1;j++){
            dp1[i][j+1] = (dp1[i][j+1] + dp0[i-1][j])%mod;
            dp1[i][j+1] = (dp1[i][j+1] + dp1[i-1][j])%mod;
            dp1[i][j+1] = (dp1[i][j+1] + dp2[i-1][j])%mod;
        }

        for(int j=0;j<=n;j++){
            if(j == 0) sum1[i][j] = dp1[i][j];
            else sum1[i][j] = (sum1[i][j-1] + dp1[i][j])%mod;
        }
    }
    int ans = 1;
    for(int i=1;i<=n;i++) ans = ans*2%mod;
    for(int j=0;j<=n;j++){
        ans = (ans - dp0[n][j] + mod)%mod;
        ans = (ans - dp1[n][j] + mod)%mod;
        ans = (ans - dp2[n][j] + mod)%mod;
    }
    printf("%d\n", ans);
}