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>

const int MAX_N = int(5e3) + 10;
const int mod = int(1e9) + 7;

int add(int a, int b) {
	return (a + b) >= mod ? a + b - mod : a + b;
}

int mul(int a, int b) {
	return 1LL * a * b % mod;
}

int sub(int a, int b) {
	return a - b < 0 ? a - b + mod : a - b;
}

int n, a, b, g[MAX_N][2], f[MAX_N][2];

int main() {
	scanf("%d%d%d", &n, &a, &b);
	if (a > b) std::swap(a, b);
	int ans = 0;
	if (b > 1) {
		f[0][0] = f[0][1] = 1;
		for (int i = 1; i <= n; ++i)
			for (int k = 0; k < 2; ++k)
				for (int j = 1; j <= i; ++j) {
					if (k == 0 && j < a) continue;
					f[i][k] = add(f[i][k], f[i - j][k ^ 1]);
				}
		f[0][0] = 0;
		for (int i = 1; i < n; ++i) {
			if (i < a) g[i][0] = 1;
			for (int j = 1; j < std::min(i, a); ++j)
				g[i][0] = add(g[i][0], g[i - j][1]);
			if (i < b)
				g[i][1] = add(f[i - 1][0], f[i - 1][1]);
			for (int j = 1; j < std::min(i, b); ++j) {
				int coef = j == 1 ? 1 : add(f[j - 2][0], f[j - 2][1]);
				g[i][1] = add(g[i][1], mul(g[i - j][0], coef));
			}
			if (n - i < b)
				ans = add(ans, mul(g[i][0], add(f[n - i - 1][0], f[n - i - 1][1])));
			if (n - i < a)
				ans = add(ans, g[i][1]);
		}
	}
	int tot = 1;
	for (int i = 1; i <= n; ++i) tot = add(tot, tot);
	printf("%d\n", add(tot, mod - ans));
}