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 <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 5005;

inline int qPow(int b, int e) {
	int a = 1;
	for (; e; e >>= 1, b = (LL)b * b % Mod)
		if (e & 1) a = (LL)a * b % Mod;
	return a;
}

int N, A, B;
int f1[MN], f2[MN], f3[MN], f4[MN];
int g1[MN], g2[MN];

int main() {
	scanf("%d%d%d", &N, &A, &B);
	if (A > B) std::swap(A, B);
	if (A == 1) return printf("%d\n", qPow(2, N)), 0;
	f1[1] = 1;
	for (int i = 2; i < B; ++i) {
		f1[i] = 1;
		for (int j = 1; j <= i - 1; ++j)
			f1[i] = (f1[i] + f2[i - j]) % Mod;
		for (int j = A; j <= i - 1; ++j)
			f2[i] = (f2[i] + f1[i - j]) % Mod;
		for (int j = 1; j <= i - 1; ++j)
			f3[i] = (f3[i] + f4[i - j]) % Mod;
		if (i >= A) f4[i] = 1;
		for (int j = A; j <= i - 1; ++j)
			f4[i] = (f4[i] + f3[i - j]) % Mod;
	}
//	for (int i = 1; i < B; ++i) printf("(f1, f2, f3, f4)[%d] = (%d, %d, %d, %d)\n", i, f1[i], f2[i], f3[i], f4[i]);
	for (int i = 1; i <= N; ++i) {
		if (i < B) g1[i] = (f1[i] + f3[i]) % Mod;
		for (int j = 1; j < B && j <= i - 1; ++j)
			g1[i] = (g1[i] + (LL)g2[i - j] * f1[j]) % Mod;
		if (i < A) g2[i] = 1;
		for (int j = 1; j < A && j <= i - 1; ++j)
			g2[i] = (g2[i] + g1[i - j]) % Mod;
//		printf("(g1, g2)[%d] = (%d, %d)\n", i, g1[i], g2[i]);
	}
	int Ans = (g1[N] + g2[N]) % Mod;
	for (int j = 1; j <= N - 1; ++j)
		Ans = (Ans + (LL)g2[N - j] * f2[j]) % Mod;
	printf("%d\n", (qPow(2, N) - Ans + Mod) % Mod);
	return 0;
}