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 <algorithm>
#include <cstdio>
#include <cstring>

const int MaxN = 5000;
const int Mod = 1000000007;

int N, A, B;
int F[MaxN + 5][2], G[MaxN + 5][2];

inline int add(int x, int y) { return (x += y) >= Mod ? x - Mod : x; }
inline int sub(int x, int y) { return (x -= y) < 0 ? x + Mod : x; }
inline int mul(int x, int y) { return 1LL * x * y % Mod; }
inline void inc(int &x, int y = 1) { (x += y) >= Mod ? x -= Mod : 0; }
inline int pw(int x, int y) { int z = 1; for (; y; y >>= 1, x = mul(x, x)) if (y & 1) z = mul(z, x); return z; }

void init() {
  scanf("%d %d %d", &N, &A, &B);
  if (A > B) std::swap(A, B);
}

void solve() {
  G[0][0] = 1;
  for (int i = 1; i < B; ++i) {
    for (int j = A; j <= i; ++j)
      G[i][0] = add(G[i][0], G[i - j][1]);
    for (int j = 1; j <= i; ++j)
      G[i][1] = add(G[i][1], G[i - j][0]);
  }
  for (int i = 1; i <= N; ++i) {
    F[i][0] = i < A;
    for (int j = 1; j < A && j < i; ++j)
      F[i][0] = add(F[i][0], F[i - j][1]);
    F[i][1] = add(G[i][0], G[i][1]);
    for (int j = 1; j < B && j < i; ++j)
      F[i][1] = add(F[i][1], mul(F[i - j][0], G[j][1]));
  }
  int ans = add(F[N][0], F[N][1]);
  for (int j = 1; j < B; ++j)
    ans = add(ans, mul(F[N - j][0], G[j][0]));
  printf("%d\n", sub(pw(2, N), ans));
}

int main() {
  init();
  solve();
  return 0;
}