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;
typedef long double ld;
const int N=500005,M=1000000007;
int n,a,b,f[5005][2],i,j,g[5005][2],dp[5005][2];
int main()
{
	scanf("%d %d %d",&n,&a,&b);
	if(a<b)
		swap(a,b);
	int s=1;
	for(i=1;i<=n;++i)
		s=s*2%M;
	if(a==1||b==1)
	{
		cout<<s;
		return 0;
	}
	f[0][0]=1;
	g[1][1]=1;
	g[0][0]=1;
	for(i=2;i<=n;++i)
	{
		for(j=i-1;j>=0;--j)
			g[i][1]=(g[i][1]+g[j][0])%M;
		for(j=i-b;j>=0;--j)
			g[i][0]=(g[i][0]+g[j][1])%M;
	}
	dp[0][1]=1;
	for(i=1;i<=n;++i)
	{
		for(j=i-1;j>=0;--j)
			dp[i][1]=(dp[i][1]+dp[j][0])%M;
		for(j=i-b;j>=0;--j)
			dp[i][0]=(dp[i][0]+dp[j][1])%M;
	}
	for(i=1;i<=n;++i)
	{
		for(j=i-1;j>=0&&j>i-b;--j)
		{
			f[i][0]=(f[i][0]+f[j][1])%M;
			if(j==0)
				++f[i][0];
		}
		for(j=i-1;j>=0&&j>i-a;--j)
		{
			f[i][1]=(f[i][1]+1ll*f[j][0]*g[i-j][1])%M;
			if(j==0)
				f[i][1]=(f[i][1]+dp[i-j][1])%M;
		}
		if(i==n)
			for(j=i-1;j>=0&&j>i-a;--j)
				f[i][1]=(f[i][1]+1ll*f[j][0]*g[i-j][0])%M;
	}
	cout<<((s-f[n][0]-f[n][1])%M+M)%M;	
}
