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;
using ll=long long;
static const ll mod=1000000007;
ll modpow(ll x,ll y){
if(y==0){
return 1;
}else if(y%2==0){
ll z=modpow(x,y/2);
  return (z*z)%mod;
}else{
ll z=modpow(x,y/2);
  return (x*((z*z)%mod))%mod;
}
}
ll N,A,B;
ll dp[2][5005][5005];
ll sum[5005];
int main(){
  cin>>N>>A>>B;
  if(A<B)swap(A,B);
  dp[1][0][0]=1;dp[0][0][0]=0;sum[0]=1;
  for(ll i=1;i<=N;i++){
    for(ll j=0;j<=min(i,A-1);j++){
    if(j!=0){
    dp[1][i][j]=(dp[1][i-1][j-1]+dp[0][i-1][j-1])%mod;
      if(B<j)
      dp[0][i][j]=dp[0][i-1][j-1];
      if(0<=j-B)
        dp[0][i][j]=(dp[0][i][j]+dp[1][i-B][j-B])%mod;
     
    }else{
   dp[0][i][0]=(sum[i-1]+dp[0][i-1][0])%mod;
      if(0<=i-B)
        dp[0][i][0]=(dp[0][i][0]-sum[i-B]+mod)%mod;
    
    }
    
    
    }ll a=0;
    for(ll j=0;j<=A-1;j++)
      a=(a+dp[1][i][j])%mod;
    sum[i]=a;
  }ll ans=0;
  for(ll j=0;j<=A-1;j++)
    ans=(ans+dp[1][N][j]+dp[0][N][j])%mod;
  ans=(mod-ans)%mod;
  ans+=modpow(2,N);ans%=mod;
  cout<<ans<<endl;
  return 0;
}