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<set>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
const int mod=1000000007;
int add(int a, int b)
{
	int c=a+b;
	if(c>=mod)c-=mod;
	return c;
}
int dif(int a, int b)
{
	int c=a-b;
	if(c<0)c+=mod;
	return c;
}
int mlt(int a, int b)
{
	long long c=a*1LL*b;
	return c%mod;
}
int bp(int a, int b)
{
	if(b==0)return 1;
	if(b%2==0)
	{
		int val=bp(a, b/2);
		return mlt(val, val);
	}
	if(b%2==1)
	{
		int val=bp(a, b-1);
		return mlt(val, a);
	}
}
int inv(int a)
{
	return bp(a, mod-2);
}
void outp(vector<vector<int>>&v)
{
	for(int i=0; i<v.size(); i++)
	{
		for(int j=0; j<v[i].size(); j++)cout<<v[i][j]<<' ';
		cout<<endl;
	}
	cout<<endl;
}
int main()
{
	int n, a, b;
	cin >> n >> a >> b;
	if (a > b)
	{
		int c = a;
		a = b;
		b = c;
	}
	vector<vector<int>> dpa(n + 1, vector<int>(n + 1)),
			dpb(n + 1, vector<int>(n + 1));
	dpb[0][0]=1;
	for(int i=1; i<=n; i++)
	{
		for(int j=max(0, i-b+1); j<i; j++)
		{
			if(i>=j+a)
			{
				if (i >= a)
				{
					dpa[i][j] = add(dpa[i - 1][j], dpb[i - a][j]);
				}
				else dpa[i][j] = dpa[i - 1][j];
			}
			dpb[i][j] = add(dpa[i - 1][j], dpb[i - 1][j]);
		}
		dpa[i][i]=dpa[i-1][i-1];
		for(int j=i-1; j>=0; j--)dpa[i][i]=add(dpa[i][i], dpb[i-1][j]);
		if(i>=a)
		{
			for (int j = i - a; j >= 0; j--)
			{
				dpa[i][i] = dif(dpa[i][i], dpb[i - a][j]);
			}
		}
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=0; j<=n; j++)
		{
	//		cout<<i<<' '<<j<<' '<<dpa[i][j]<<' '<<dpb[i][j]<<endl;
		}
	}
	int ans=bp(2, n);
	for(int i=0; i<=n; i++)
	{
		ans=dif(ans, dpa[n][i]);
		ans=dif(ans, dpb[n][i]);
	}
	if(a>1)
	{
		cout << ans << endl;
	}
	else cout<<bp(2,n)<<endl;
}