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<iostream>
#include<iomanip>
#include<cassert>
#include<stdexcept>
#include<utility>
#include<functional>
#include<numeric>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<array>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<complex>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<bitset>
#include<memory>
using namespace std;
using ll=long long;

const ll MOD=1e9+7;
void add(ll& lhs,ll rhs){
    lhs=(lhs+rhs)%MOD;
}
int main(){
    int n,a,b;
    cin>>n>>a>>b;
    if(b<a) swap(a,b);
    if(a==1 || b==1){
        ll res = 1;
        for(int i=0;i<n;i++){
            res=res*2%MOD;
        }
        cout<<res<<endl;
        return 0;
    }
    vector<vector<ll>> Adp(n+1,vector<ll>(b));
    vector<vector<ll>> Bdp(n+1,vector<ll>(b));
    vector<vector<ll>> Cdp(n+1,vector<ll>(b));
    vector<ll> ok(n+1);
    Adp[0][0] = 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<a;j++){
            if(j+1<a){
                add(Adp[i+1][j+1],Adp[i][j]);
            }
            add(Bdp[i+1][1],Adp[i][j]);
            if(i==0 && j==0){
                if(a==b){
                    add(ok[i+a],Adp[i][0]);
                }
                else{
                    add(Cdp[i+a][a],Adp[i][0]);
                }
            }
        }
        for(int j=0;j<b;j++){
            add(Adp[i+1][1],Bdp[i][j]);
            if(j+1<b){
                add(Bdp[i+1][j+1],Bdp[i][j]);
            }
            else{
                add(ok[i+1],Bdp[i][j]);
            }
            if(i+a<=n){
                if(j+a<b){
                    add(Cdp[i+a][j+a],Bdp[i][j]);
                }
                else{
                    add(ok[i+a],Bdp[i][j]);
                }
            }
        }        
        for(int j=0;j<b;j++){
            if(j+1<b){
                add(Bdp[i+1][j+1],Cdp[i][j]);
                add(Cdp[i+1][j+1],Cdp[i][j]);
            }
            else{
                add(ok[i+1],Cdp[i][j]);
                add(ok[i+1],Cdp[i][j]);
            }
        }
        add(ok[i+1],ok[i]);
        add(ok[i+1],ok[i]);
    }

    cout<<ok[n]<<endl;
    
    return 0;
}