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 N=5e3+10;
const int mod=1e9+7;

int gi() {
	int x=0,o=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int add(int a,int b) {
	return a+b>=mod?a+b-mod:a+b;
}

int n,a,b,f[N][N][2],g[N],sum[N][N][2];

int getsum(int i,int j,int k) {
	if(i<0||j<0) return 0;
	if(sum[i][j][k]!=-1) return sum[i][j][k];
	return sum[i][j][k]=add(f[i][j][k],getsum(i-1,j-1,k));
}

int main() {
	cin>>n>>a>>b;if(a>b) swap(a,b);
	memset(sum,-1,sizeof(sum));
	f[0][0][0]=f[0][0][1]=g[0]=1;
	for(int i=1;i<=n;i++)
		for(int j=0;j<b;j++) {
			f[i][j][1]=getsum(i-1,j-1,0);
			if(j) f[i][j][0]=getsum(i-a,j-a,1);
			else for(int k=0;k<a&&k<=i;k++) f[i][j][0]=add(f[i][j][0],g[i-k]);
			g[i]=add(g[i],f[i][j][1]);
		}
	int ans=0;
	for(int i=0;i<b;i++) ans=(0ll+ans+f[n][i][0]+f[n][i][1])%mod;
	int bin=1;
	for(int i=1;i<=n;i++) bin=2ll*bin%mod;
	cout<<(bin-ans+mod)%mod;
	return 0;
}
