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 sz(x) ((int) ((x).size()))
typedef long long ll;
typedef long double ld;

const int mod = 1e9 + 7;
int n, l[2], p[5100], dp[3][5100][5100], ps[5100];

int add(int a, int b) {
  a += b;
  if (a >= mod)
    a -= mod;
  return a;
}

int sub(int a, int b) {
  a -= b;
  if (a < 0)
    a += mod;
  return a;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  cin >> n >> l[0] >> l[1];
  p[0] = 1;
  for (int i = 0; i < n; i++)
    p[i + 1] = add(p[i], p[i]);
  if (l[0] < l[1])
    swap(l[0], l[1]);
  int res = 0;
  dp[0][0][0] = 1;
  for (int i = 0; i <= n; i++) {
    ps[i + 1] = add(ps[i + 1], ps[i]);
    dp[1][i][0] = add(dp[1][i][0], ps[i]);
    for (int j = 0; j <= i && j < l[0]; j++) {
      dp[0][i + 1][j + 1] = add(dp[0][i + 1][j + 1], dp[0][i][j]);
      dp[0][i + 1][j + 1] = add(dp[0][i + 1][j + 1], dp[1][i][j]);
      dp[0][i + 1][j + 1] = add(dp[0][i + 1][j + 1], dp[2][i][j]);
      dp[2][i + 1][j + 1] = add(dp[2][i + 1][j + 1], dp[2][i][j]);
      if (i + l[1] <= n)
        dp[2][i + l[1]][j + l[1]] = add(dp[2][i + l[1]][j + l[1]], dp[0][i][j]);
      ps[i + 1] = add(ps[i + 1], dp[0][i][j]);
      if (i + l[1] <= n)
        ps[i + l[1]] = sub(ps[i + l[1]], dp[0][i][j]);
    }
  }
  for (int k = 0; k < 3; k++)
    for (int i = 0; i <= n; i++)
      for (int j = l[0]; j <= n; j++)
        res = add(res, ((ll) dp[k][i][j] * p[n - i]) % mod);
  cout << res << "\n";
}
