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;

const int P = 1e9 + 7;
int upd(int x){return x + (x >> 31 & P);}
void inc(int &a , int b){a = upd(a + b - P);}
int sub(int a , int b){return upd(a - b);}
int dp[5003][5003][2] , sum[10003][2] , sum1[10003][2] , N , A , B;

int main(){
	cin >> N >> A >> B; dp[0][0][0] = 1; if(A > B) swap(A , B);
	for(int i = 1 ; i <= N ; ++i){
		if(i - A - 1 >= 0){int pre = i - A - 1; for(int j = 0 ; j <= pre ; ++j) for(int k = 0 ; k < 2 ; ++k) inc(sum[pre - j][k] , dp[pre][j][k]);}
		for(int j = 1 ; j <= i ; ++j)
			for(int k = 0 ; k < 2 ; ++k){
				inc(dp[i][j][k | (j >= B)] , dp[i - 1][j - 1][k]);
				inc(dp[i][j][k | (j >= B)] , sum[i - j][k]);
				inc(dp[i][1][k | (1 >= B)] , sub(sum1[i - j][k] , sum[i - j][k]));
			}
		int pre = i - 1; for(int j = 0 ; j <= pre ; ++j) for(int k = 0 ; k < 2 ; ++k) inc(sum1[pre - j][k] , dp[pre][j][k]);
	}
	int sum = 0;
	for(int i = 0 ; i <= N ; ++i)
		for(int j = 0 ; j <= i ; ++j)
			for(int k = 0 ; k < 2 ; ++k)
				if(k || (j + (N - i >= A ? N - i : 0) >= B))
					inc(sum , dp[i][j][k]);
	cout << sum; 
	return 0;
}