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;

const int N = 5005;
const int md = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= md) {
    x -= md;
  }
  if (x < 0) {
    x += md;
  }
  return x;
}

inline void sadd(int &x, int y) { x = add(x, y); }

int dp[2][N][N];
int pref[2][N][N];
int sum[2][N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, A, B;
  cin >> n >> A >> B;
  if (A > B) swap(A, B);
  dp[0][0][0] = dp[1][0][0] = 1;
  pref[0][0][0] = pref[1][0][0] = 1;
  sum[0][0] = sum[1][0] = 1;
  for (int i = 1; i <= n; i++) {
    sum[0][i] = sum[0][i - 1];
    sum[1][i] = sum[1][i - 1];
    for (int j = 0; j < min(i + 1, B); j++) {
      if (j >= A) {
        dp[0][i][j] = pref[1][i - j][i - A];
      }
      if (j == 0) {
        dp[0][i][j] = add(sum[1][i - 1], i >= A ? -sum[1][i - A] : 0);
      }
      dp[1][i][j] = pref[0][i - j][i - 1];
      sadd(sum[0][i], dp[0][i][j]);
      sadd(sum[1][i], dp[1][i][j]);
    }
    for (int t : {0, 1}) {
      for (int d = 0; d <= i; d++) {
        pref[t][d][i] = add(pref[t][d][i - 1], dp[t][i][i - d]);
      }
    }
  }
  int res = 1;
  for (int i = 0; i < n; i++) {
    sadd(res, res);
  }
  for (int r = 0; r < B; r++) {
    sadd(res, -dp[0][n][r]);
    sadd(res, -dp[1][n][r]);
  }
  cout << res << '\n';
  return 0;
}
