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<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
const int MOD=1000000007;
int n,a,b;
long long f[N][2];
long long g[N];
long long dp[N][2];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
int main()
{
	scanf("%d%d%d",&n,&a,&b);
	if(a>b) swap(a,b);
	if(b==1)
	{
		printf("%lld",ksm(2,n));
		return 0;
	}
	f[0][0]=f[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<i;j++)
			f[i][1]=(f[i][1]+f[j][0])%MOD;
		for(int j=0;j+a<=i;j++)
			f[i][0]=(f[i][0]+f[j][1])%MOD;
	}
	g[0]=1;
	for(int i=1;i<=n;i++)
		g[i]=(f[i][0]+f[i][1])%MOD;
	long long ans=0;
	for(int i=1;i<n;i++)
	{
		if(i<a) dp[i][0]=(dp[i][0]+1)%MOD;
		for(int j=i-a+1;j<i;j++)
			if(j>0) dp[i][0]=(dp[i][0]+dp[j][1])%MOD;
		if(i<b) dp[i][1]=(dp[i][1]+g[i-1])%MOD;
		for(int j=i-b+1;j<i;j++)
			if(j>0) dp[i][1]=(dp[i][1]+dp[j][0]*(i-j==1?1:g[i-j-2])%MOD)%MOD;
		if(i+b-1>=n) ans=(ans+dp[i][0]*g[n-i-1]%MOD)%MOD;
		if(i+a-1>=n) ans=(ans+dp[i][1])%MOD;
	}
	printf("%lld",(ksm(2,n)-ans+MOD)%MOD);
	return 0;
}