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<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll dp1[2][15050][2];
ll dp2[15050][2];
int main()
{
	int num, a, b;
	scanf("%d%d%d", &num, &a, &b);
	if (a > b)swap(a, b);
	for (int k = 0; k < 2; k++)
	{
		dp1[k][0][k] = 1;
		for (int i = 0; i < num; i++)
		{
			for (int j = a; i + j <= num; j++)dp1[k][i + j][0] = (dp1[k][i + j][0] + dp1[k][i][1]) % mod;;
			dp1[k][i + 1][1] = (dp1[k][i + 1][1] + dp1[k][i][0] + dp1[k][i][1]) % mod;
		}
	}
	//for (int k = 0; k < 2; k++)for (int i = 0; i <= num; i++)for (int j = 0; j < 2; j++)printf("%d %d %d  %lld\n", k, i, j, dp1[k][i][j]);
	dp2[0][0] = dp2[0][1] = 1;
	for (int i = 0; i < num; i++)
	{
		for (int j = 1; j < a; j++)
		{
			dp2[i + j][0] = (dp2[i + j][0] + dp2[i][1]) % mod;
		}
		for (int j = 1; i + j <= num && j <= b - 1; j++)
		{
			int z1 = 0;
			if (i == 0)z1 = 1;
			if (i + j != num)
			{
				dp2[i + j][1] = (dp2[i + j][1] + dp2[i][0] * dp1[z1][j][1]) % mod;
			}
			else
			{
				dp2[i + j][1] = (dp2[i + j][1] + dp2[i][0] * (dp1[z1][j][0] + dp1[z1][j][1])) % mod;
			}
		}
	//	printf("%lld %lld\n", dp2[i + 1][0], dp2[i + 1][1]);
	}
	ll s = 1;
	for (int i = 0; i < num; i++)s = s * 2 % mod;
	printf("%lld\n", (s + mod + mod - dp2[num][0] - dp2[num][1]) % mod);
}