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 ll long long

const int N = 5005, P = 1000000007;
int n, a, b, f[N], ff[N], g[N][2];
int Pow(ll x, int y){
	int ans=1;
	for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
	return ans;
}
int main() {
	scanf("%d%d%d", &n, &a, &b);
	if(a>b) swap(a, b);
	f[1]=1;
	for(int i=1; i<b; ++i){
		(f[i+1]+=f[i])%=P;
		for(int j=a+1; i+j<=b; ++j) (f[i+j]+=f[i])%=P, (ff[i+j-1]+=f[i])%=P;
	}
	g[0][0]=g[0][1]=1;
	for(int i=0; i<n; ++i){
		(g[i][1]+=ff[i])%=P;
		for(int j=1; j<a && i+j<=n; ++j) (g[i+j][0]+=g[i][1])%=P;
		for(int j=1; j<b && i+j<=n; ++j) g[i+j][1]=(g[i+j][1]+(ll)g[i][0]*f[j])%P;
		g[n][1]=(g[n][1]+(ll)g[i][0]*ff[n-i])%P;
	}
	printf("%lld\n", ((ll)Pow(2, n)-g[n][0]-g[n][1]+P+P)%P);
	return 0;
}