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<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#include<assert.h>
#include<chrono>
#include<random>
#include<iostream>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define SZ(x) ((int)x.size())
#define VI vector<int>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
template<typename T>inline void chkmin(T &x,T y){x=x<y?x:y;}
template<typename T>inline void chkmax(T &x,T y){x=x>y?x:y;}
const int MAXN=5005;
const int mod=1e9+7;
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void dl(int &x,int y){x-=y;if(x<0)x+=mod;}
int coef[MAXN],encoef[MAXN],n,A,B;
//end is 0
void getcoef()
{
	coef[1]=1;
	for(int i=1;i<A;i++)
	{
		ad(coef[i+1],coef[i]); 
		for(int j=B;i+j<=A;j++)ad(coef[i+j+1],coef[i]),ad(encoef[i+j],coef[i]);
	}
}
int f[MAXN][2];//end with 0/1
int main()
{
	#ifdef Rose
		double BeginJudgeTime=clock();
	#endif
	n=read();A=read();B=read();if(A<B)swap(A,B);
	getcoef();
	for(int i=0;i<B;i++)f[i][1]=1;
	for(int i=1;i<A;i++)f[i][0]=encoef[i];
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<A&&i+j<=n;j++)
		{
			ad(f[i+j][0],1LL*f[i][1]*coef[j]%mod);
			if(i+j==n)ad(f[i+j][1],1LL*f[i][1]*encoef[j]%mod);
		}
		for(int j=1;j<B&&i+j<=n;j++)
			ad(f[i+j][1],f[i][0]);
	}
	int ans=1;
	for(int i=1;i<=n;i++)ans=2LL*ans%mod;
	dl(ans,f[n][0]);dl(ans,f[n][1]);
	pr2(ans);
	#ifdef Rose
		double EndJudgeTime=clock();
		cerr<<"JudgeTime is"<<" ";
		cerr<<(EndJudgeTime-BeginJudgeTime)/CLOCKS_PER_SEC<<endl;
	#endif
	return 0;
}
