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 <algorithm>
using namespace std;

const long long mod = 1000000007;
int n, a, b; long long d[2][5050], e[2][5050];

void add(long long& a, long long b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}

int main()
{
	scanf ("%d %d %d", &n, &a, &b);

	long long all = 1;
	for (int i = 0; i < n; i++) all = all * 2 % mod;

	long long ans = 0;

	if (a > 1 && b > 1){
		if (a < b) swap(a, b);
		d[0][1] = 1;
		for (int i = 1; i < a; i++){
			add(d[0][i + 1], d[0][i]);
			add(d[0][i + 1], d[1][i]);
			if (i + b < a) add(d[1][i + b], d[0][i]);
			add(d[1][i + 1], d[1][i]);
		}

		e[0][0] = e[1][0] = 1;
		for (int j = 1; j < a; j++) e[0][j] = d[1][j];
		for (int i = 0; i < n; i++){
			for (int j = 1; j < a && i + j <= n; j++) add(e[0][i + j], e[1][i] * d[0][j] % mod);
			for (int j = 1; j < b && i + j <= n; j++) add(e[1][i + j], e[0][i]);
		}

		add(ans, e[0][n]);
		add(ans, e[1][n]);
		for (int j = 1; j < a; j++) add(ans, e[1][n - j] * d[1][j] % mod);
	}

	ans = all + mod - ans;
	if (ans >= mod) ans -= mod;

	printf ("%lld\n", ans);

	return 0;
}