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 int long long 
const int mod=1e9+7;
int f[5005][2],g[5005],dp[5005][2];
signed main(){
	int sum=0,ans=1;
	int n,A,B;
	cin>>n>>A>>B;
	if(A>B) swap(A,B);
	f[0][0]=f[0][1]=1;g[0]=1;
	for(int i=1;i<=n;++i){
		for(int j=A;j<=i;++j)
			f[i][0]=(f[i][0]+f[i-j][1])%mod;
		for(int j=1;j<=i;++j)
			f[i][1]=(f[i][1]+f[i-j][0])%mod;
		g[i]=(f[i][0]+f[i][1])%mod;
	}
	for(int i=1;i<n;++i){
		if(i<A) dp[i][0]=1;
		if(i<B) dp[i][1]=f[i][1];
		for(int j=1;j<min(i,A);++j)
			dp[i][0]=(dp[i][0]+dp[i-j][1])%mod;
		for(int j=1;j<min(i,B);++j)
			dp[i][1]=(dp[i][1]+dp[i-j][0]*((j<2)?1:g[j-2])%mod)%mod;
		if(n-i<A) sum=(sum+dp[i][1])%mod; //后面全是0
		if(n-i<B) sum=(sum+dp[i][0]*g[n-i-1]%mod)%mod; //后面是方案，防止重复往后面加一个 1 的分隔符 
	}
	for(int i=1;i<=n;++i) ans=ans*2ll%mod;
	ans=(ans-sum+mod)%mod;
	cout<<ans;
	return 0;
} 