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<algorithm>
using namespace std;
const int mod=1000000007;
inline void add(int &x,int y){(x+=y)>=mod?x-=mod:0;}
inline int pl(int x,int y){return (x+=y)>=mod?x-mod:x;}
int kpow(int a,int b)
{
	int s=1;
	for(;b;b>>=1,a=1ll*a*a%mod)
		if(b&1)s=1ll*s*a%mod;
	return s;
}
int n,a,b,f[5050][2],g[5050],dp[5050][2],ans;
int main()
{
	scanf("%d %d %d",&n,&a,&b);
	if(a>b)swap(a,b);
	if(b>=2)
	{
		f[0][0]=f[0][1]=1;
		for(int i=1;i<=b;++i)
			for(int j=1;j<=i;++j)
			{
				if(j>=a)add(f[i][0],f[i-j][1]);
				add(f[i][1],f[i-j][0]);
			}
		g[0]=1;
		for(int i=1;i<=b;++i)g[i]=pl(f[i][0],f[i][1]);
	//	for(int i=1;i<=b;++i)printf("%d ",g[i]);printf("\n");
		dp[0][0]=dp[0][1]=1;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=i;++j)
			{
				if(j<b)dp[i][1]=(dp[i][1]+1ll*dp[i-j][0]*g[max(j-(i!=j)-(i!=n),0)])%mod;
				if(j<a)add(dp[i][0],dp[i-j][1]);
			}
	//	for(int i=1;i<=n;++i)printf("%d %d\n",dp[i][0],dp[i][1]);
		ans=pl(dp[n][0],dp[n][1]);
	}
	printf("%d",pl(kpow(2,n),mod-ans));
	return 0;
}