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 maxn=5005;
const int mod=1e9+7;
int n,a,b;
int f[maxn][maxn],sum[maxn],sf[maxn][maxn];

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

int main(){
	scanf("%d%d%d",&n,&a,&b);
	int ans=1;
	for(int i=1;i<=n;i++)ans=2LL*ans%mod;
	if(a<b)swap(a,b);
	f[0][0]=sf[0][0]=sum[0]=1;
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1];
		for(int j=0;j<=i&&j<a;j++){
			if(j==0){
				f[i][j]=(i<b);
				if(i>=2)Add(f[i][j],(sum[i-2]-(i-b-1<0?0:sum[i-b-1])+mod)%mod);
			}
			else{
				f[i][j]=f[i-1][j-1];
				if(i==j&&i>=b)Add(f[i][j],1);
				if(j>=b+1)Add(f[i][j],sf[i-j][j-(b+1)]);
			} 
			sf[i-j][j]=(!j?0:sf[i-j][j-1]);
			Add(sf[i-j][j],f[i][j]);
			if(j+1<a)Add(sum[i],f[i][j]);
		}
	}
	for(int i=0;i<a;i++)ans=(ans+mod-f[n][i])%mod;
	printf("%d\n",ans);
	return 0;
}