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>
using namespace std;
const int mod=1e9+7;
int n,a,b,dp[5555][5555][2],sum[5555][5555][2],sm[5555],ans,pw;
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	if (a>b) swap(a,b);
	dp[0][0][0]=dp[0][0][1]=1;
	sum[0][0][0]=sum[0][0][1]=1;
	sm[0]=1;
	for (int i=1;i<=n;i++)
	{
		for (int j=max(0,i-b+1);j<=i;j++)
		{
			for (int k=0;k<2;k++)
			{
				if (!k && i==j)
				{
					dp[i][j][k]=sm[i-1];
					if (i-a>=0) dp[i][j][k]=(dp[i][j][k]-sm[i-a])%mod;
				}
				else
				{
					if (!k)
					{
						if (i-a<0) dp[i][j][k]=0;
						else dp[i][j][k]=sum[i-a][j][1];
					}
					else
					{
						dp[i][j][k]=sum[i-1][j][0];
					}
				}
			}
		}
		sm[i]=sm[i-1];
		for (int j=0;j<=i;j++)
		{
			for (int k=0;k<2;k++)
			{
				sum[i][j][k]=(sum[i-1][j][k]+dp[i][j][k])%mod;
				if (k==1) sm[i]=(sm[i]+dp[i][j][k])%mod;
			}
		}
	}
	for (int i=n-b+1;i<=n;i++)
	{
		ans=(ans+dp[n][i][0])%mod;
		ans=(ans+dp[n][i][1])%mod;
	}
	pw=1;
	for (int i=1;i<=n;i++) pw=(pw+pw)%mod;
	ans=(pw-ans)%mod;
	printf("%d\n",(ans+mod)%mod);
	return 0;
}