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=5010,mod=1000000007;
inline void Add(int &a,int b){a=a+b>=mod?a+b-mod:a+b;}
inline int ksm(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) res=1ll*res*a%mod;
	return res;
}
int N,A,B,f[5010][2],F[5010][2],ans;
inline int getv(int x){return x<=2?1:(f[x-2][0]+f[x-2][1])%mod;}
int main()
{
	cin>>N>>A>>B;if(A>B) swap(A,B);f[0][0]=f[0][1]=1;
	for(int i=0;i<N;i++) for(int j=i+1;j<=N;j++)
	{
		Add(f[j][0],f[i][1]);
		if(j-i>=A) Add(f[j][1],f[i][0]);
	}
	for(int i=1;i<N;i++)
	{
		if(i<A) Add(F[i][0],1);
		if(i<B) Add(F[i][1],getv(i+1));
		for(int j=1;j<min(i,A);j++) Add(F[i][0],F[i-j][1]);
		for(int j=1;j<min(i,B);j++) Add(F[i][1],1ll*F[i-j][0]*getv(j)%mod);
		if(N-i<A) Add(ans,F[i][1]);
		if(N-i<B) Add(ans,1ll*F[i][0]*getv(N-i+1)%mod);
	}
	cout<<(ksm(2,N)-ans+mod)%mod<<endl;
}