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>
#define mo 1000000007
#define ll long long
using namespace std;
ll dp[100010],d1[100010][2],n,A,B;
void add(ll &x,ll y){x=(x+y)%mo;}
ll po(ll y){ll z=1;for (int i=1;i<=y;i++)z=z*2%mo;return z;}
int main(){
	cin>>n>>A>>B;
	if (A<B) swap(A,B);
	dp[1]=1;
	for (int i=1;i<A;i++){add(dp[i+1],dp[i]);for (int j=i+B+1;j<=A;j++)add(dp[j],dp[i]);}
	for (int i=1;i<A;i++)d1[i][0]=dp[i+1];
	for (int i=1;i<B;i++)d1[i][1]=1;
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<i+A;j++)if (j==n)add(d1[j][0],d1[i][1]*dp[j-i+1]);else add(d1[j][0],d1[i][1]*dp[j-i]);
		for (int j=i+1;j<i+B;j++)add(d1[j][1],d1[i][0]);
	}
	cout<<(po(n)-d1[n][0]-d1[n][1]+mo+mo)%mo<<endl;
	return 0;
}