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;
typedef long long ll;
const ll M = 1e9+7;
const int MN = 5010;
ll dp[2][2][MN];
ll ew[MN];
int main() {
	ll n,a,b;
	cin >> n >> a >> b;
	if(a > b) {swap(a,b);}
	int cu = 0;
	memset(dp,0,sizeof(dp));
	dp[cu][0][0] = 1;
	memset(ew,0,sizeof(ew));
	ew[0] = 1;
	for(int i=0;i<=n;i++) {
		ew[i+1] += ew[i];
		if(ew[i+1] >= M) {ew[i+1] -= M;}
		for(int j=a;j+i+1<=n;j++) {
			ew[i+j+1] += ew[i];
			if(ew[i+j+1] >= M) {ew[i+j+1] -= M;}
		}
	}
	for(int i=0;i<n;i++) {
		int nu = 1-cu;
		memset(dp[nu],0,sizeof(dp[nu]));
		for(int j=0;j<a;j++) {
			dp[nu][0][j+1] += dp[cu][0][j];
			if(dp[nu][0][j+1] >= M) {dp[nu][0][j+1] -= M;}
			dp[nu][1][1] += dp[cu][0][j];
			if(dp[nu][1][1] >= M) {dp[nu][1][1] -= M;}
		}
		for(int j=0;j<b;j++) {
			dp[nu][1][j+1] += dp[cu][1][j];
			if(dp[nu][1][j+1] >= M) {dp[nu][1][j+1] -= M;}
			ll tr = dp[cu][1][j];
			if(j == i) {
				tr = tr*ew[max(j,0)]%M;
			} else {
				tr = tr*ew[max(j-1,0)]%M;
			}
			dp[nu][0][1] += tr;
			if(dp[nu][0][1] >= M) {dp[nu][0][1] -= M;}
		}
		cu = nu;
	}
	ll res = 0;
	for(int i=0;i<a;i++) {
		res += dp[cu][0][i];
	}
	for(int i=0;i<b;i++) {
		ll tr = dp[cu][1][i];
		tr = tr*ew[max(i,0)]%M;
		res += tr;
	}
	res %= M;
	ll go = 1;
	for(int i=0;i<n;i++) {
		go *= 2;
		if(go >= M) {go -= M;}
	}
	res = go-res;
	res = ((res%M)+M)%M;
	cout << res << '\n';
}
