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;
int const p=1e9+7;
int f[5005][2],g[5005][2];
int mod(int x){return x>=p?x-p:x;}
int main()
{
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);
    if(a>b)swap(a,b);
    g[1][1]=1;
    for(int i=2;i<b;i++)
    {
        for(int j=1;j<=i-a;j++)
            g[i][0]=mod(g[i][0]+g[j][1]);
        g[i][1]=mod(g[i-1][0]+g[i-1][1]);
    }
    f[0][0]=f[0][1]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=max(i-a+1,0);j<i;j++)f[i][0]=mod(f[i][0]+f[j][1]);
        for(int j=max(i-b+1,0);j<i;j++)
        {
            if(i==n)f[i][0]=(f[i][0]+1ll*f[j][0]*g[i-j][0])%p;
            if(j==0)f[i][1]=(1ll*f[i][1]+g[i][0]+g[i][1])%p;
            else f[i][1]=(f[i][1]+1ll*f[j][0]*g[i-j][1])%p;
        }
    }
    int pw=1;
    for(int i=1;i<=n;i++)pw=mod(pw+pw);
    printf("%lld",(1ll*pw+p+p-f[n][0]-f[n][1])%p);
    return 0;
}