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;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000000000000

void get(int N,int A,int B){
	int a=0,b=0;
	for(int i=0;i<(1<<N);i++){
		string s = "";
		for(int j=0;j<N;j++){
			if((i>>j)&1)s += '0';
			else s += '1';
		}

		for(int j=0;j<N;j++){
			if(j+A-1>=N)break;
			bool f = true;
			for(int k=0;k<A;k++){
				if(s[j+k]!='0'){
					f=false;
					break;
				}
			}
			if(f){
				for(int k=j;k<N;k++){
					if(s[k]=='0')s[k]='1';
					else break;
				}
			}
		}
		bool f = false;
		for(int j=0;j<N;j++){
			if(j+B-1>=N)break;
			bool F = true;
			for(int k=0;k<B;k++){
				if(s[j+k]!='1'){
					F=false;
					break;
				}
			}
			if(F)f=true;
		}
		if(!f){
			if(i%2==0)a++;
			else b++;
		}
	}
	
	cout<<a<<','<<b<<endl;
}

int main(){
	
	int N,A,B;
	cin>>N>>A>>B;
	if(A>B)swap(A,B);
	
	int t = 1;
	for(int i=0;i<N;i++)t = mod(t*2);
	
	vector<vector<int>> cnt(N+1,vector<int>(2,0));
	cnt[0][1] = 1;
	for(int i=0;i<N;i++){
		cnt[i+1][1] = mod(cnt[i+1][1] + cnt[i][1]);
		
		for(int j=A;true;j++){
			if(i+j>N)break;
			cnt[i+j][0] = mod(cnt[i+j][0] + cnt[i][1]);
		}
		
		for(int j=A+1;true;j++){
			if(i+j>N)break;
			cnt[i+j][1] = mod(cnt[i+j][1] + cnt[i][1]);
		}
	}
	
	vector<vector<int>> dp(N+1,vector<int>(2,0));
	dp[0][0] = 1;
	dp[0][1] = 1;
	
	for(int i=0;i<N;i++){
		for(int j=1;j<A;j++){
			if(i+j<=N)dp[i+j][0] = mod(dp[i+j][0] + dp[i][1]);
		}
		if(i!=0){
			for(int j=1;j<B;j++){
				if(i+j<N)dp[i+j][1] = mod(dp[i+j][1] + mod(cnt[j-1][1]*dp[i][0]));
				if(i+j==N){
					dp[i+j][1] = mod(dp[i+j][1] + mod((cnt[j-1][0]+cnt[j-1][1])*dp[i][0]));
				}
			}
		}
		else{
			for(int j=1;j<B;j++){
				if(i+j<N)dp[i+j][1] = mod(dp[i+j][1] + mod(cnt[j][1]*dp[i][0]));
			}
		}

	}
	
	int ans = 0;
	ans = mod(ans + dp.back()[0] + dp.back()[1]);
	ans = mod(t-ans);
	
	//get(N,A,B);
	
	//t = mod(t-mod(dp.back()[0]+dp.back()[1]));
	
	cout<<ans<<endl;
	
	return 0;
}
