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>
const int mo=1e9+7,N=5005;
int n,a,b,i,j,k,l,f1[N],f2[N],g[N][2][2],ans;
inline void add(int&a,const int&b){a+=b-mo;a+=a>>31&mo;}
int main(){
	scanf("%d%d%d",&n,&a,&b);if(a<b)std::swap(a,b);
	for(i=1;i<=n;++i)f1[i]=1;
	for(i=1;i<n;++i)for(j=b+1;i+j<=n;++j)f1[i+j]=(f1[i+j]+1ll*f1[i]*(j-b))%mo;
	for(i=b+1;i<=n;++i)f2[i]=i-b;
	for(i=1;i<n;++i)for(j=b+1;i+j<=n;++j)f2[i+j]=(f2[i+j]+1ll*f2[i]*(j-b))%mo;
	for(i=1;i<=n;++i)add(f2[i],f1[i]);
	g[0][1][0]=1;
	for(i=1;i<=n;++i)g[i][1][i>=a]=f2[i];
	for(i=0;i<=n;++i){
		for(j=1;j<b && i+j<=n;++j)for(k=0;k<2;++k)add(g[i+j][0][k],g[i][1][k]);
		for(j=1;i+j<=n;++j)for(k=0;k<2;++k)add(g[i+j][1][k|(j>=a)],1ll*(i+j==n?f2[j]:f1[j])*g[i][0][k]%mo);
	}
	for(i=b;i<=n;++i)for(j=b;i+j+1<=n;++j)ans=(ans+f1[n-i-j])%mo;
	for(j=b;j+1<=n;++j)ans=(ans+f1[n-j])%mo;
	ans=(1ll*ans+1+g[n][0][1]+g[n][1][1])%mo;
	printf("%d\n",ans);
}