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;
using LL = long long;
constexpr int maxn = 5000 + 10;
constexpr int mod = 1000000007;
int N, A, B;
void add(int& x, int y){
    x += y;
    if(x >= mod) x -= mod;
}
int dp[maxn + 1][maxn + 1];
int sumh[maxn + 1][maxn + 1];
int shit[maxn + 1][maxn + 1];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> N >> A >> B;
    if(A < B) swap(A, B);
    dp[0][0] = 1;
    for(int i = 0; i <= N; i += 1)
        for(int j = 0; j <= i; j += 1){
            add(dp[i][j], shit[i][j]);
            add(dp[i][j], sumh[i][j]);
            add(shit[i + 1][j + 1], shit[i][j]);
            add(sumh[i + 1][j], sumh[i][j]);
            {
                int ni = i + 1;
                int nj = j + 1;
                add(dp[ni][nj], dp[i][j]);
            }
            {
                int ni = i + B + 1;
                int nj = j + B + 1;
                add(shit[ni][nj], dp[i][j]);
            }
            {
                int ni1 = i + 2;
                int ni2 = i + B + 1;
                int nj = j >= A ? j : 1;
                add(sumh[ni1][nj], dp[i][j]);
                add(sumh[ni2][nj], (mod - dp[i][j]) % mod);
            }
            int ni = N;
            int nj = j >= A ? j : (N - i >= B ? j + N - i : 0);
            add(dp[ni][nj], dp[i][j]);
        }
    int ans = 0;
    for(int i = A; i <= N; i += 1) add(ans, dp[N][i]);
    cout << (LL)ans * (mod + 1) / 2 % mod << "\n";
    return 0;
}