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 f[10101][2];
int g[10101][2];
int dp[5050][2];

int _2[5050];

int main()
{
	int N, A, B;
	scanf("%d%d%d", &N, &A, &B);
	
	if(A > B)
		swap(A, B);
	
	_2[0] = 1;
	for(int i = 1; i <= 5000; i++)
		_2[i] = _2[i - 1] * 2 % mod;
	f[0][0] = 1;	
	for(int i = 1; i < A + B; i++)
	{
		for(int j = A; j <= ((i <= B) ? i : A); j++)
		{
			f[i][0] += f[i - j][1];
			if(f[i][0] >= mod)
				f[i][0] -= mod;
		}
		if(i <= B)
		{
			for(int j = 1; j <= B; j++)
			{
				f[i][1] += f[i-j][0];
				if(f[i][1] >= mod)
					f[i][1] -= mod;
			}
		}
	}
	g[0][1] = 1;	
	for(int i = 1; i < A + B; i++)
	{
		for(int j = A; j <= ((i <= B) ? i : A); j++)
		{
			g[i][0] += g[i - j][1];
			if(g[i][0] >= mod)
				g[i][0] -= mod;
		}
		if(i <= B)
		{
			for(int j = 1; j <= B; j++)
			{
				g[i][1] += g[i - j][0];
				if(g[i][1] >= mod)
					g[i][1] -= mod;
			}
		}
	}
	dp[0][0] = dp[0][1] = 1;
	for(int i = 1; i <= N; i++)
	{
		if(i < B)
		{
			dp[i][1] += g[i][1];
			if(dp[i][1] >= mod)
				dp[i][1] -= mod;
		}
		for(int j = 1; j < min(i + 1, B); j++)
		{
			dp[i][1] += 1ll * f[j][1] * dp[i - j][0] % mod;
			if(dp[i][1] >= mod)
				dp[i][1] -= mod;
		}
		for(int j = 1; j < min(i + 1, A); j++)
		{
			dp[i][0] += dp[i - j][1];
			if(dp[i][0] >= mod)
				dp[i][0] -= mod;
		}
	}
	int ans = 0;
	for(int i = 0; i <= N; i++)
	{
		if(i == 0)
		{
			for(int j = B; j < A + B; j++)
			if(i + j <= N)
			{
				ans += 1ll * dp[i][1] * (g[j][0] + g[j][1]) % mod * _2[N - i - j] % mod;
				if(ans >= mod)
					ans -= mod;
			}
		}
		for(int j = B; j < A + B; j++)
		if(i + j <= N)
		{
			ans += 1ll * dp[i][0] * (f[j][0] + f[j][1]) % mod * _2[N - i - j] % mod;
			if(ans >= mod)
				ans -= mod; 
		}
	}
	printf("%d\n", ans);
	return 0;
}