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 long long LL;
const int N = 5000 + 10;
typedef long long LL;
const LL MOD = 1e9 + 7;
int n, A, B;
LL f[N][N][2];
LL g[N][N][2], w[N][2];
void add(LL & x, LL y) {
	x += y;
	if (x > MOD) x -= MOD;
}
int main() {
	cin >> n >> A >> B;
	if (A < B) swap(A, B);
	LL tot = 1;
	for (int i = 1; i <= n; i ++) tot = tot * 2 % MOD;
	
	f[0][0][0] = 1; g[0][0][0] = 1; w[0][0] = 1;
	f[0][0][1] = 1; g[0][0][1] = 1; w[0][1] = 1;

	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j < A; j ++) {
			if (i>=1 && j>=1) {
				add(f[i][j][0], g[i-1][j-1][1]);
			}
			if (i-B>=0 && j-B>=0) {
				add(f[i][j][1], g[i-B][j-B][0]);
			}
		}
		for (int t = 1; t <= min(i, B - 1); t ++) {
			add(f[i][0][1], w[i-t][0]);
		}
		g[i][0][1] = f[i][0][1];
		for (int j = 1; j < A; j ++) {
			g[i][j][0]=(g[i-1][j-1][0]+f[i][j][0])%MOD;
			g[i][j][1]=(g[i-1][j-1][1]+f[i][j][1])%MOD;
		}
		
		for(int j = 0; j < A; j ++) {
			add(w[i][0], f[i][j][0]);
			add(w[i][1], f[i][j][1]);
		}
	}
	for (int j = 0; j < A; j ++) {
		for (int k = 0; k < 2; k ++) {
			tot = tot - f[n][j][k];
			tot = (tot % MOD + MOD)	% MOD;	
		}
	}
	cout << tot << endl;
}