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 = 5e3 + 5;
const int mod = 1e9 + 7;
inline int pls( int a , int b ) { a += b - mod; return a + ( a >> 31 & mod ); }
inline int mns( int a , int b ) { a -= b; return a + ( a >> 31 & mod ); }
inline void inc( int & a , int b ) { a += b - mod; a += a >> 31 & mod; }
inline void dec( int & a , int b ) { a -= b; a += a >> 31 & mod; }

int A , B , n , ans;
int f[N] , g[N][2];

int main( void ) {
  cin >> n >> A >> B; 
  if( A > B ) swap( A , B );
  ans = 1;
  for( int i = 1 ; i <= n ; ++i ) ans = pls( ans , ans );
  if( B == 1 ) return printf("%d",ans) , 0;
  f[0] = 1;
  for( int i = 1 ; i <= B ; ++i ) {
    f[i] = f[i - 1];
    for( int j = A ; j <= i ; ++j ) {
      if( j ^ i ) inc( f[i] , f[i - j - 1] );
      else inc( f[i] , 1 );
    }
  }
  g[0][0] = 1;
  for( int i = 1 ; i < B ; ++i )
    g[i][0] = f[i - 1];
  for( int i = 1 ; i <= n ; ++i ) {
    for( int j = 1 ; j < B && j <= i ; ++j )
      inc( g[i][0] , 1LL * g[i - j][1] * ( j == 1 ? 1 : f[j - 2] ) % mod );
    for( int j = 1 ; j < A && j <= i ; ++j )
      inc( g[i][1] , g[i - j][0] );
  }
  dec( ans , g[n][1] );
  for( int i = 1 ; i < B && i <= n ; ++i )
    dec( ans , 1LL * g[n - i][1] * f[i - 1] % mod );
  printf("%d",ans);
  return 0;
}
