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>
#define SIZE 5005
#define MOD 1000000007
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll way[SIZE];
ll way2[SIZE];
ll way3[SIZE];
ll dp[SIZE][2];

int main()
{
	int n,A,B;
	scanf("%d %d %d",&n,&A,&B);
	if(A>B) swap(A,B);
	for(int i=1;i<B;i++)
	{
		way[i]=1;
		for(int j=1;j+A+1<=i;j++)
		{
			ll vl=way[j]*(ll) (i-j-A)%MOD;
			way[i]+=vl;
			if(way[i]>=MOD) way[i]-=MOD;
		}
	}
	for(int i=1;i<B;i++)
	{
		way3[i]=0;
		for(int j=A;j<i;j++)
		{
			way3[i]+=way[i-j];
			if(way3[i]>=MOD) way3[i]-=MOD;
		}
	}
	way2[0]=1;
	for(int i=1;i<B;i++)
	{
		way2[i]=0;
		for(int j=0;j+A+1<=i;j++)
		{
			ll vl=way2[j]*(ll) (i-j-A)%MOD;
			way2[i]+=vl;
			if(way2[i]>=MOD) way2[i]-=MOD;
		}
	}
	dp[0][0]=1;
	for(int i=0;i<B;i++) dp[i][1]=way2[i];
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(j-i<B)
			{
				dp[j][1]+=dp[i][0]*way[j-i]%MOD;
				if(dp[j][1]>=MOD) dp[j][1]-=MOD;
			}
			if(j-i<A)
			{
				dp[j][0]+=dp[i][1];
				if(dp[j][0]>=MOD) dp[j][0]-=MOD;
			}
		}
	}
	ll ret=(dp[n][0]+dp[n][1])%MOD;
	for(int i=A;i<n;i++)
	{
		ret+=dp[n-i][0]*way3[i]%MOD;
		if(ret>=MOD) ret-=MOD;
	}
	ll all=1;
	for(int i=0;i<n;i++) all=all*2LL%MOD;
	printf("%lld\n",(all-ret+MOD)%MOD);
}