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;

typedef double D;
typedef long long int LL;

#define st first
#define nd second
#define PLL pair <LL, LL>
#define PII pair <int, int>

const int N = 5007;
const int MX = 1e9 + 7;
const LL INF = 1LL * MX * MX;

int n, a, b;
int dp[N][N][3];

void add(int &a, int b){
	a += b;
	if(a >= MX)
		a -= MX;
}

int main(){
	scanf("%d %d %d", &n, &a, &b);
	if(a > b)
		swap(a, b);

	if(a == 1){
		int ans = 1;
		while(n--)
			add(ans, ans);
		printf("%d\n", ans);
		exit(0);
	}

	dp[1][a - 1][0] = 1;
	dp[1][b - 1][1] = 1;
	dp[a][0][2] = 1;
	
	for(int i = 1; i < n; ++i){
		for(int c = 0; c < 3; ++c)
			add(dp[i + 1][0][2], dp[i][0][c]);
		
		for(int c = 0; c < 3; ++c)
			if(i + 1 < b)
				add(dp[i + 1][b - i - 1][1], dp[i][0][c]);
			else
				add(dp[i + 1][0][2], dp[i][0][c]);
		
		for(int j = 1; j < b && n - i >= j; ++j){
			{	//c = 0
				if(j > 1)
					add(dp[i + 1][j - 1][0], dp[i][j][0]);
				add(dp[i + 1][b - 1][1], dp[i][j][0]);
			}
			
			{	//c = 1
				add(dp[i + 1][j - 1][1], dp[i][j][1]);
				if(i + a <= n)
					add(dp[i + a][max(j - a, 0)][2], dp[i][j][1]);
				add(dp[i + 1][a - 1][0], dp[i][j][1]);
			}
			
			{	//c = 2
				add(dp[i + 1][j - 1][2], dp[i][j][2]);
				add(dp[i + 1][j - 1][1], dp[i][j][2]);
			}
		}
	}
	
	int ans = 0;
	for(int c = 0; c < 3; ++c)
		add(ans, dp[n][0][c]);
	printf("%d\n", ans);
	return 0;
}