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;
typedef pair<int,int>pii;
const int mn=5e3+10;
const ll inf=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
ll dp[mn][mn],p1[mn][mn],p2[mn][mn];
int main(){
    cin.tie(0);
    cin.sync_with_stdio(0);
    int n,a[2];
    cin>>n>>a[0]>>a[1];
    if(a[0]>a[1])swap(a[0],a[1]);
    dp[0][0]=p1[0][0]=p2[0][0]=1;
    ll ans=1;
    for(int i=1;i<=n;i++){
        ans*=2,ans%=mod;
        for(int j=0;j<=min(i,a[1]-1);j++){
            if(j==1){
                for(int k=0;k<=i;k++){
                    dp[i][j]+=(i>=2?p1[i-2][k]:0)-(i>=a[0]+1?p1[i-a[0]-1][k]:0);
                }
                dp[i][j]%=mod;
            }
            dp[i][j]+=(i>=a[0]+1?p2[i-a[0]-1][i-j]:0);
            dp[i][j]+=j?dp[i-1][j-1]:0;
            dp[i][j]%=mod;
            p1[i][j]=(p1[i-1][j]+dp[i][j])%mod;
            p2[i][i-j]=(p2[i-1][i-j]+dp[i][j])%mod;
        }
    }
    for(int i=0;i<=n;i++){
        int na=n-i;
        if(na<a[0]){
            for(int j=0;j<=i;j++)ans-=dp[i][j],ans%=mod;
        }
        else{
            for(int j=0;j+na<a[1];j++)ans-=dp[i][j],ans%=mod;
        }
    }
    if(ans<0)ans+=mod;
    printf("%lld",ans);
}