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 maxN = 5005, mod = 1e9 + 7;

int n, A, B;
int f[maxN + 1][2], g[maxN + 1][2], h[maxN + 1];

inline int ADD(int x, int y) { return x + y >= mod ? x + y - mod : x + y; }

inline int SUB(int x, int y) { return x - y < 0 ? x - y + mod : x - y; }

int main()
{
	scanf("%d %d %d", &n, &A, &B);

	if(A > B) swap(A, B);

	g[1][1] = 1;
	for(int i = 2; i <= B - 1; i++)
	{
		g[i][1] = ADD(g[i - 1][0], g[i - 1][1]);
		for(int j = A; j <= i; j++)
			g[i][0] = ADD(g[i][0], g[i - j][1]);
	}

	for(int i = A + 1; i <= B - 1; i++) h[i] = ADD(h[i - 1], g[i - A][1]);

	f[0][0] = f[0][1] = 1;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= min(i, A - 1); j++) f[i][0] = ADD(f[i][0], f[i - j][1]);
		for(int j = 1; j <= min(i, B - 1); j++)
		{
			if(i == n) f[i][1] = ADD(f[i][1], 1ll * f[i - j][0] * g[j][0] % mod);
			if(j == i) f[i][1] = ADD(f[i][1], 1ll * f[i - j][0] * h[j] % mod); 
			f[i][1] = ADD(f[i][1], 1ll * f[i - j][0] * g[j][1] % mod);
		}
	}

	int ans = 1;
	for(int i = 1; i <= n; i++) ans = 2ll * ans % mod;
	ans = SUB(ans, ADD(f[n][0], f[n][1]));

	printf("%d\n", ans);
	return 0;
}
