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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define mod 1000000007
#define maxn 5010

int n,a,b;
int ksm(int x,int y){int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}
int g[maxn][2],f[maxn][2];
void add(int &x,int y){x=(x+y>=mod?x+y-mod:x+y);}

int main()
{
	scanf("%d %d %d",&n,&a,&b);
	if(a>b)swap(a,b); g[1][1]=1;
	for(int i=2;i<b;i++)
	{
		g[i][1]=(g[i-1][0]+g[i-1][1])%mod;
		for(int j=a;j<i;j++)add(g[i][0],g[i-j][1]);
	}
	f[0][0]=f[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<min(a,i+1);j++)add(f[i][0],f[i-j][1]);
		for(int j=1;j<min(b,i+1);j++)
		{
			if(i==n)add(f[i][0],1ll*f[i-j][0]*g[j][0]%mod);
			if(i==j)add(f[i][1],(g[j][0]+g[j][1])%mod);
			else add(f[i][1],1ll*f[i-j][0]*g[j][1]%mod);
		}
	}
	printf("%d",(ksm(2,n)-(f[n][0]+f[n][1])%mod+mod)%mod);
}