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;

template<int MOD>
struct ModInt {
   using Mint = ModInt;
   int val;
   ModInt(ll __val = 0) { fix(__val % MOD + MOD); }
   Mint& fix(int __val) { val = __val; if (val >= MOD) val -= MOD; return *this; }
   explicit operator int() { return val; }
   Mint operator + (const Mint &mt) const { return Mint().fix(val + mt.val); }
   Mint operator - (const Mint &mt) const { return Mint().fix(val - mt.val + MOD); }
   Mint operator * (const Mint &mt) const { return Mint().fix(ll(val) * mt.val % MOD + MOD); }
   Mint& operator += (const Mint &mt) { return *this = *this + mt; }
   Mint& operator -= (const Mint &mt) { return *this = *this - mt; }
   Mint& operator *= (const Mint &mt) { return *this = *this * mt; }
   Mint pow(int y) const {
      Mint x = *this;
      Mint ans(1);
      for (; y > 0; y >>= 1, x *= x) {
         if (y & 1) ans *= x;
      }
      return ans;
   }
   Mint operator -() const { return Mint().fix(MOD - val); }
   Mint inv() const { return pow(MOD - 2); }
   Mint operator / (const Mint &mt) const { return *this * mt.inv(); }
   Mint& operator /= (const Mint &mt) const { return *this / mt; }
   friend ostream& operator<<(ostream& os, const Mint& mt) { return os << mt.val; }
};

using Mint = ModInt<1000000007>;

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   int N, A, B;
   cin >> N >> A >> B;
   if (A > B) swap(A, B);
   vector<array<Mint, 2>> ways(B + 1);
   ways[0][0] = 1;
   ways[0][1] = 1;
   for (int b = 1; b <= B; ++b) {
      for (int i = 1; i <= b; ++i) ways[b][1] += ways[b - i][0];
      for (int a = A; a <= b; ++a) ways[b][0] += ways[b - a][1];
   }
   vector<Mint> tot(B + 1);
   for (int i = 1; i <= B; ++i) tot[i] = ways[i][0] + ways[i][1];
   tot[0] = 1;
   Mint ans = Mint(2).pow(N);
   vector<array<Mint, 2>> dp(N + 1);
   for (int n = 1; n < N; ++n) {
      if (n < A) dp[n][0] += 1;
      for (int i = 1; i < min(n, A); ++i) dp[n][0] += dp[n - i][1];
      if (n < B) dp[n][1] += tot[n - 1];
      for (int i = 1; i < min(n, B); ++i) {
         Mint g = (i == 1) ? Mint(1) : tot[i - 2];
         dp[n][1] += dp[n - i][0] * g;
      }
      if (N - n < B) ans -= dp[n][0] * tot[N - n - 1];
      if (N - n < A) ans -= dp[n][1];
   }
   cout << ans << "\n";
   return 0;
}
