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
#define f(i, x, n) for (int i = x; i < (int)(n); ++i)

int const N = 5000, md = 1e9 + 7;
int dp[2][N + 1][N + 1], s[2][N + 1][N + 1], p2[N + 1];

void ad(int &x, int y) { if ((x += y) >= md)x -= md; }

int gt(int tp, int a, int b) { return b >= 0 ? s[tp][a][b] : 0; }

int sm(int tp, int a, int b, int l, int r){
	int an = gt(tp, a - l, b - l) - gt(tp, a - r - 1, b - r - 1);
	ad(an, md);
	return an;
}

int main(){
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	p2[0] = 1;
	f(i, 1, n + 1)ad(p2[i] = p2[i - 1], p2[i - 1]);
	if (a < b)swap(a, b);
	
	f(tp, 0, 2)dp[tp][0][0] = s[tp][0][0] = 1;
	f(i, 1, n + 1)f(j, 0, i + 1)f(tp, 0, 2){
		if (j < a){
			if (tp == 0)dp[tp][i][j] = sm(1, i, j, 1, j);
			else {
				dp[tp][i][j] = sm(0, i, j, min(j + 1, b), j);
				if (j == 0)f(k, 0, i + 1)ad(dp[tp][i][j], sm(0, i, k, 1, min(b - 1, k)));
			}
		}
		ad(s[tp][i][j] = dp[tp][i][j], j == 0 ? 0 : s[tp][i - 1][j - 1]);
	}
	int an = 0;
	f(i, 0, 2)f(j, 0, a)ad(an, dp[i][n][j]);
	an = p2[n] - an;
	ad(an, md);
	printf("%d\n", an);
}