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 <cstdio>
#include <iostream>
#define MN 5010
#define mod 1000000007

int f[MN][MN][2], s[MN];
int sum[MN][2], mi[MN];

int inc(int a, int b) {return (a += b) >= mod ? a - mod : a;}

int main()
{
	int n, a, b; scanf("%d%d%d", &n, &a, &b);
	if(a > b) std::swap(a, b);
	mi[0] = 1; for(int i = 1; i <= n; i++) mi[i] = mi[i - 1] * 2 % mod;
	f[0][0][0] = f[0][0][1] = s[0] = 1;
	sum[0][1] = 1;
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= std::min(b, i); j++)
		{
			if(j == b)
				ans = (ans + 1ll * mi[n - i] * (sum[i - j][0] + sum[i - j][1])) % mod;
			else
			{
				f[i][j][0] = sum[i - j][1];
				f[i][j][1] = sum[i - j][0];
				s[i] = inc(s[i], f[i][j][0]);
			}
		}
		for(int j = std::max(i - a + 1, 0); j < i; j++)
			f[i][0][1] = inc(f[i][0][1], s[j]);
		if(i - a >= 0)
		{
			for(int j = 0; j <= i - a; j++)
			{
				if(j + a < b)
					f[i][j + a][1] = inc(f[i][j + a][1], f[i - a][j][0]);
				else 
					ans = (ans + 1ll * mi[n - i] * f[i - a][j][0]) % mod;
				
				sum[i - a - j][0] = inc(sum[i - a - j][0], f[i - a][j][0]);
			}
		}
		for(int j = 0; j <= i; j++)
			sum[i - j][1] = inc(sum[i - j][1], f[i][j][1]);
	}
	printf("%d\n", ans);
}

/*考虑检查一种方案是否合法
倒推，相当于把A个0或B个1替换成任意数字
假设 A<=B ，否则相当于初始全为1，然后交换A，B
序列合法当且仅当把所有>=A的0连续段给替换为1后存在>=B的1连续段
充分性就是存在>=B的1连续段后把这个段给全部赋值成0与左右两段0合并
由于B>=A，所以新的0段也可以全部赋成1然后继续搞
必要性就是如果不存在，那除了那些0段可以随便填以外无法进行任何操作，从而无解，逆否命题可知必要性成立
f[i][j + i - k][0] = sigma f[k][j][1]
j + i - k > B 的状态不转移 (=B的状态单独处理，直接对答案贡献)

f[i][0][1] = sigma f[i - A + 1 ~ i][j][0] 长度不够

f[i][j + i - k][1] = sigma f[k][j][0] k < i - A (k = i - A 单独处理，直接对答案贡献)
j + i - k > B 的状态不转移 (=B的状态单独处理，直接对答案贡献)
*/