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<algorithm>
#include<vector>
using namespace std;
int n,a,b,dp[2][2][5005],dp2[2][2][5005],ans=0;
const int mod=1e9+7;
int M(int x){return x>=mod?x-mod:x;}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	if(a>b)swap(a,b);
	for(int i=a;i<=n;i++)dp[0][0][i]=1;
	for(int i=1;i<=n;i++)dp[1][1][i]=1;
	for(int i=1;i<n;i++)
	{
		for(int u=0;u<2;u++)
		{
			for(int j=a;j<=n-i;j++)dp[u][0][i+j]=M(dp[u][0][i+j]+dp[u][1][i]);
			for(int j=1;j<=n-i;j++)dp[u][1][i+j]=M(dp[u][1][i+j]+dp[u][0][i]);
		}
	}
	for(int i=1;i<a;i++)dp2[0][0][i]=1;
	for(int i=1;i<b;i++)dp2[0][1][i]=M(dp[0][1][i]+dp[1][1][i]);
	for(int i=b;i<n;i++)dp2[1][1][i]=M(dp[0][1][i]+dp[1][1][i]);
	dp2[1][1][n]=M(M(dp[0][1][n]+dp[0][0][n])+M(dp[1][0][n]+dp[1][1][n]));
	for(int i=1;i<=n;i++)
	{
		for(int u=0;u<2;u++)
		{
			for(int j=1;j<=n-i&&j<b;j++)
			{
				dp2[u][1][i+j]=(1ll*dp2[u][1][i+j]+1ll*dp[1][1][j]*dp2[u][0][i])%mod;
				if(i+j==n)dp2[u][0][i+j]=(1ll*dp2[u][0][i+j]+1ll*dp[1][0][j]*dp2[u][0][i])%mod;
			}
			for(int j=b;j<=n-i;j++)
			{
				dp2[1][1][i+j]=(1ll*dp2[1][1][i+j]+1ll*dp[1][1][j]*dp2[u][0][i])%mod;
				if(i+j==n)dp2[1][0][i+j]=(1ll*dp2[1][0][i+j]+1ll*dp[1][0][j]*dp2[u][0][i])%mod;
			}
			for(int j=1;j<a&&j<=n-i;j++)dp2[u][0][i+j]=M(dp2[u][0][i+j]+dp2[u][1][i]);
		}
	}
	for(int i=0;i<2;i++)ans=M(ans+dp2[1][i][n]);
	printf("%d\n",ans);
	return 0;
}