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<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int Mod=1000000007;
int A,B;
int f[5010][5010];
int g[5010][5010];
int sumg[5010];
int sumg2[5010][5010];
int F(int n,int x);
int G(int n,int x);
int SumG(int n);
int SumG2(int n,int x);
int F(int n,int x)
{
	if(n<=0||x<0)return 0;
	if(f[n][x]!=-1)
		return f[n][x];
	f[n][x]=(SumG(n-1)-SumG(n-B)+Mod)%Mod;
	if(x>=B)f[n][x]=(f[n][x]+SumG2(n-B,x-B))%Mod;
	return f[n][x];
}
int G(int n,int x)
{
	if(n<0||x<0)return 0;
	if(n==0)return 1;
	if(g[n][x]!=-1)
		return g[n][x];
	return g[n][x]=(G(n-1,x-1)+F(n-1,x-1))%Mod;
}
int SumG(int n)
{
	if(n<0)return 0;
	if(sumg[n]!=-1)
		return sumg[n];
	return sumg[n]=(SumG(n-1)+G(n,A-1))%Mod;
}
int SumG2(int n,int x)
{
	if(n<0||x<0)return 0;
	if(sumg2[n][x]!=-1)
		return sumg2[n][x];
	return sumg2[n][x]=(SumG2(n-1,x-1)+G(n,x))%Mod;
}
int main()
{
	memset(f,-1,sizeof(f));
	memset(g,-1,sizeof(g));
	memset(sumg,-1,sizeof(sumg));
	memset(sumg2,-1,sizeof(sumg2));
	int n;scanf("%d %d %d",&n,&A,&B);
	if(A<B)swap(A,B);
	int ans=1;
	for(int i=1;i<=n;i++)
		ans=ans*2ll%Mod;
	ans=(ans-F(n,A-1)+Mod)%Mod;
	ans=(ans-G(n,A-1)+Mod)%Mod;
	printf("%d\n",ans);
	return 0;
}