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 f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr ll MOD = 1e9+7;

inline ll pw(ll base, ll exp) {
	ll res = 1;
	while (exp) {
		if (exp & 1) (res *= base) %= MOD;
		exp >>= 1, (base *= base) %= MOD;
	}
	return res;
}

inline ll inv(ll x) { return pw(x, MOD - 2); }

ll F[5005][2], G[5005], DP[5005][2];

int main() {
    if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N, A, B; cin >> N >> A >> B;
    if (A > B) swap(A, B);

    if (B == 1) {
        cout << pw(2, N);
        return 0;
    }

    F[0][0] = F[0][1] = 1;
    for (int i = 1; i <= N; ++i)
        for (int d : { 0, 1 })
            for (int j = 1; j <= i; ++j)
                if (d == 1 || j >= A) (F[i][d] += F[i-j][!d]) %= MOD;
    
    G[0] = 1;
    for (int i = 1; i <= N; ++i) G[i] = F[i][0]+F[i][1];

    ll ans = 0;
    for (int i = 1; i < N; ++i) {
        if (i < A) ++DP[i][0];
        for (int j = 1; j < min(i, A); ++j) (DP[i][0] += DP[i-j][1]) %= MOD;
        if (i < B) (DP[i][1] += G[i-1]) %= MOD;
        for (int j = 1; j < min(i, B); ++j) (DP[i][1] += DP[i-j][0]*(j==1?1:G[j-2])) %= MOD;
        if (N-i < B) (ans += DP[i][0]*G[N-i-1]) %= MOD;
        if (N-i < A) (ans += DP[i][1]) %= MOD;
    }

    //for (int i = 0; i <= N; ++i) cout << DP[i][0] << ' ' << DP[i][1] << '\n';
    cout << (pw(2, N)-ans+MOD)%MOD;
}
