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 int N=5005,p=1000000007;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int qpow(int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
int n,A,B,dp[N][2],f[N],s[N],g[N],gg[N];
void check(int &x,int y){if ((x+=y)>=p) x-=p;}
int main(){
	n=read();A=read();B=read();
	if (A>B) swap(A,B);
	
	f[0]=1;
	for (int i=1;i<B;i++){
		memcpy(s,f,sizeof(s));
		for (int j=0;i+j<B;j++){
			check(g[i+j],f[j]);
			check(s[j+1],s[j]);
			if (j>=A) check(f[j],s[j-A]);
		}
	}
	memcpy(s,g,sizeof(s));
	for (int i=1;i<B;i++){
		gg[i]=g[i];
		check(s[i],s[i-1]);
		if (i>=A) check(gg[i],s[i-A]);
	}
	for (int i=1;i<A;i++) dp[i][0]=1;
	for (int i=1;i<B;i++) dp[i][1]=gg[i];
	for (int i=1;i<=n;i++){
		for (int j=1;(j<A)&&(i+j<=n);j++) check(dp[i+j][0],dp[i][1]);
		for (int j=1;(j<B)&&(i+j<=n);j++) check(dp[i+j][1],(ll)dp[i][0]*((i+j==n) ? gg[j] : g[j])%p);
	}
	int ans=qpow(2,n);
	check(ans,p-dp[n][0]);
	check(ans,p-dp[n][1]);
	printf("%d\n",ans);
	return 0;
}