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

long long mod = 1000000007;
long long N, A, B;
long long dp[6009][6009][2];
long long ru[6009][6009];
long long power[6009];
long long Answer;

void init() {
	power[0] = 1;
	for (int i = 1; i <= 5000; i++) power[i] = (2LL * power[i - 1]) % mod;
}

void solve(int pos) {
	// 累積和を取る
	for (int i = 0; i <= N; i++) {
		ru[pos][i] = ru[pos - 1][i];
		ru[pos][i] += dp[pos - 1][i][0];
		ru[pos][i] %= mod;
	}

	// 長い方を使う場合
	for (int i = 0; i <= N; i++) {
		dp[pos][i][0] += dp[pos - 1][i][1];
		dp[pos][i][0] += dp[pos - 1][i][0];
		dp[pos][i][0] %= mod;
		if ((pos - i) >= A) {
			Answer += dp[pos][i][0] * power[N - pos];
			Answer %= mod;
			dp[pos][i][0] = 0;
		}
	}

	// 短い方を使う場合（そして失敗する場合）
	long long rem = 0;
	for (int i = 0; i <= N; i++) {
		int cl = max(0LL, pos - B + 1), cr = max(-1, pos - 1);
		rem += (ru[cr + 1][i] - ru[cl][i] + mod) % mod;
		rem %= mod;
	}
	dp[pos][pos][1] = rem;

	// 短い方を使う場合（そして成功する場合）
	for (int i = 0; i <= N; i++) {
		int cr = max(-1LL, pos - B);
		long long val = ru[cr + 1][i];
		dp[pos][i][1] += val;
		if ((pos - i) >= A) {
			Answer += dp[pos][i][1] * power[max(0LL, N - pos - 1)];
			Answer %= mod;
			dp[pos][i][1] = 0;
		}
	}
}

int main() {
	cin >> N >> A >> B;
	if (A < B) swap(A, B);
	init();

	dp[0][0][0] = 1;
	for (int i = 1; i <= N; i++) solve(i);
	cout << Answer << endl;
	return 0;
}