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<iostream> 
#define RI register int
#define CI const int&
using namespace std;
const int N=5005,mod=1e9+7;
int n,a,b,f[N][2],g[N],dp[N][2],ans;
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int sum(CI x,CI y)
{
	int t=x+y; return t>=mod?t-mod:t;
}
inline int sub(CI x,CI y)
{
	int t=x-y; return t<0?t+mod:t;
}
inline int quick_pow(int x,int p,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
int main()
{
	RI i,j; scanf("%d%d%d",&n,&a,&b); if (a>b) swap(a,b);
	if (b==1) return printf("%d",quick_pow(2,n)),0;
	for (f[0][0]=f[0][1]=i=1;i<=n;++i) for (j=1;j<=i;++j)
	{
		if (j>=a) inc(f[i][0],f[i-j][1]); inc(f[i][1],f[i-j][0]);
	}
	for (g[0]=i=1;i<=n;++i) g[i]=sum(f[i][0],f[i][1]);
	for (i=1;i<n;++i) 
	{
		if (i<a) dp[i][0]=1; for (j=1;j<min(i,a);++j) inc(dp[i][0],dp[i-j][1]);
		if (i<b) dp[i][1]=g[i-1]; for (j=1;j<min(i,b);++j)
		inc(dp[i][1],1LL*dp[i-j][0]*(j<=2?1:g[j-2])%mod);
		if (n-i<a) inc(ans,dp[i][1]); if (n-i<b) inc(ans,1LL*dp[i][0]*g[n-i-1]%mod);
	}
	return printf("%d",sub(quick_pow(2,n),ans)),0;
}