Problem:
 Score : 800 points    Problem Statement 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) .        Sample Input 1 4 2 3      Sample Output 1 11  For example, x can be 0011 or 1111 in the end, but cannot be 0110 .       Sample Input 2 10 7 2      Sample Output 2 533       Sample Input 3 1000 100 10      Sample Output 3 828178524

Solution (Python):
N,A,B=map(int,input().split())
mod=10**9+7

A,B=min(A,B),max(A,B)

data=[0]*B
data[0]=1
for i in range(1,B):
    data[i]=(data[i-1]+sum(data[i-1-k] for k in range(A,i)))%mod



dp=[0]*(N+1)
dp[0]=1
imos=[0]*(N+1)
imos[0]=1

for i in range(1,N+1):
    if i!=N:
        for j in range(1,min(i,B)):
            
            R=i-j-1
            L=i-j-min(A,i-j+1)
            if R>L:
                if L>-1:
                    dp[i]+=(imos[R]-imos[L])*data[j-1]
                else:
                    dp[i]+=imos[R]*data[j-1]
                dp[i]%=mod
        if B>i:
            dp[i]+=data[i]
            dp[i]%=mod
    else:
        for j in range(B):
            
            R=i-j-1
            L=i-j-min(A,i-j+1)
            if R>L:
                if L>-1:
                    dp[i]+=(imos[R]-imos[L])*data[j]
                else:
                    dp[i]+=imos[R]*data[j]
                dp[i]%=mod
        
        
    imos[i]=dp[i]
    imos[i]+=imos[i-1]
    imos[i]%=mod



print((pow(2,N,mod)-dp[N])%mod)

Solution (Python):

"""
Writer: SPD_9X2

すべて0にする、すべて1にするは自明に可能
なので A >= B としてよい(A<Bの時は01を入れ替えて考えればよい)

最後に置いた場所の周囲がどんな状況か考える

0*Aがある場合、その周囲はすべての場合構成可能
ない場合は…？
1*Bがある場合を考える。長さB以上の1列は後からおけるからおｋだが…
長さB以上の1をすべて0に変えたときに、長さA以上の0があればおｋ

どう数え上げる？
ダメな場合を引くのがよさそう？
→dp[i][last][num] = i番目まで見て、lastを現在num個連続しておいている場合の通り数
ただし、dp[?][1][B-1]はdp[?][0][B]に伝播する
これまずいか

ブロックで考えるやり方はどうなんだろう
つまり、連鎖を断ち切れるのは長さB以下の1列だけ

0 or B以上連続する1の列のみで構成されたブロックX(Yに隣接する端は0である必要あり)
B未満の1列であるブロックYを交互に置いていく

dp[i][XorY] = i番目の文字を次に置けるとき、最後に置いたブロックがXorYの時の通り数
初期値は
dp[0][X] = 1
dp[0][Y] = 1 ←これ、かなり注意する必要がある左端が1でもいいから
同様に、Nに移行する時にXを置くときも右端を1にできるのに注意

B以上連続する1を0に変えるとすべて0になる文字列の数をまず求める
上と同様にブロックdp?
0のブロックは,1以上のどんな長さでも置ける
1のブロックは,B以上の長さ置ける
dp[0][Z] = 1
dp[0][O] = 1

"""

N,A,B = map(int,input().split())

fdp = [[0,0] for i in range(N+1)]
fdp[0] = [1,1]
mod = 10**9+7

if A < B:
    tmp = B
    B = A
    A = tmp

for i in range(N):

    for j in range(i+1,N+1):
        fdp[j][0] += fdp[i][1]
        fdp[j][0] %= mod

    for j in range(i+B,N+1):
        fdp[j][1] += fdp[i][0]
        fdp[j][1] %= mod



dp = [[0,0] for i in range(N+1)]
dp[0] = [1,1]

for i in range(N):

    for j in range(i+1,min(N+1,i+B)):
        dp[j][1] += dp[i][0]
        dp[j][1] %= mod

    
    for j in range(i+1,min(N+1,i+A)):

        l = j-i

        if i == 0 or j == N:
            if l == 1:
                dp[j][0] += dp[i][1]
                dp[j][0] %= mod
            else:
                dp[j][0] += dp[i][1] * sum(fdp[l-1])
                dp[j][0] %= mod

        else:
            if l <= 2:
                dp[j][0] += dp[i][1]
                dp[j][0] %= mod
            else:
                dp[j][0] += dp[i][1] * sum(fdp[l-2])
                dp[j][0] %= mod


print ((pow(2,N,mod)-sum(dp[N])) % mod)

Solution (Python):
MOD = 10 ** 9 + 7
n, a, b = map(int, input().split())

if a > b:
    a, b = b, a

dp_1s = [0] * b
for l in range(a + 2, b):
    dp = [[0, 0] for _ in range(l + 1)] 
    dp[1][1] = 1
    for i in range(1, l):
        dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % MOD
        dp[i + 1][1] = (dp[i + 1][1] + dp[i][0] + dp[i][1]) % MOD
        if i + a < l:
            dp[i + a][0] = (dp[i + a][0] + dp[i][1]) % MOD
    dp_1s[l] = dp[l][1] - 1

dp_0s_edge = [0] * b
for l in range(a + 1, b):
    dp = [[0, 0] for _ in range(l + 1)]
    dp[a][0] = 1
    for i in range(1, l):
        dp[i + 1][0] = (dp[i + 1][0] + dp[i][0]) % MOD
        dp[i + 1][1] = (dp[i + 1][1] + dp[i][0] + dp[i][1]) % MOD
        if i + a < l:
            dp[i + a][0] = (dp[i + a][0] + dp[i][1]) % MOD
    dp_0s_edge[l] = dp[l][1] 



dp = [[0, 0] for _ in range(n + 1)]

dp[0] = [1, 1]

for l in range(a + 1, b):
    dp[l][1] = dp_0s_edge[l]

for i in range(n):
    for j in range(i + 1, min(n + 1, i + b)):
        dp[j][1] = (dp[j][1] + dp[i][0]) % MOD
    for j in range(i + 1, min(n + 1, i + a)):
        dp[j][0] = (dp[j][0] + dp[i][1]) % MOD
    for l in range(a + 2, b):
        if i + l <= n:
            dp[i + l][1] = (dp[i + l][1] + dp[i][0] * dp_1s[l]) % MOD


for l in range(a + 1, b):
    dp[n][0] = (dp[n][0] + dp[n - l][0] * dp_0s_edge[l]) % MOD

print((pow(2, n, MOD) - sum(dp[n])) % MOD)

Solution (Python):
def solve(n, a, b):
    MOD = 10 ** 9 + 7
    if a > b:
        a, b = b, a
    if a == 1:
        return pow(2, n, MOD)

    
    
    
    dp1 = [0] * (b + 1)
    dp1_acc = [0] * (b + 1)
    dp1[0] = 1
    dp1_acc[0] = 1

    for i in range(1, b + 1):
        tmp = dp1[i - 1]  
        if i - a - 1 >= 0:
            tmp = (tmp + dp1_acc[i - a - 1]) % MOD  
        dp1[i] = tmp
        dp1_acc[i] = (dp1_acc[i - 1] + tmp) % MOD
    
    
    

    
    
    
    
    dp20 = [0] * (n + 1)
    dp21 = [0] * (n + 1)
    dp21_acc = [0] * (n + 1)
    dp20[0] = dp21[0] = dp21_acc[0] = 1
    for i in range(1, n + 1):
        t0 = dp21_acc[i - 1]
        if i >= a:
            t0 -= dp21_acc[i - a]
        dp20[i] = t0 % MOD

        t1 = 0
        for j in range(1, min(i + 1, b)):
            t1 += dp20[i - j] * dp1[j - 1]
        
        if i < b:
            t1 += dp1[i] - dp1[i - 1]
        t1 %= MOD
        dp21[i] = t1
        dp21_acc[i] = (dp21_acc[i - 1] + t1) % MOD

    disable = dp20[n] + dp21[n]

    
    
    for i in range(1, b):
        disable += dp20[n - i] * (dp1[i] - dp1[i - 1])

    return (pow(2, n, MOD) - disable) % MOD


n, a, b = map(int, input().split())
print(solve(n, a, b))

Solution (Python):


n,aa,bb = list(map(int, input().split()))

a = max(aa,bb)
b = min(aa,bb)
p = 1000000007

xs0 = [0]*(n+1)
os0 = [0]*(n+1)

os0[0] = 1

for i in range(b,a-1):
    for j in range(b,i+1):
        xs0[i] += os0[i-j]
        xs0[i] %= p
    for j in range(1,i+1):
        os0[i] += xs0[i-j]
        os0[i] %= p





os = [0]*a

for i in range(b,a-2): 
    for j in range(2,a-i): 
        os[i+j] += xs0[i] * (j-1)

x = [0]*(n+1)
o = [0]*(n+1)

for i in range(b+1,a): 
    for j in range(b,i): 
        o[i] += xs0[j]
        o[i] %= p

x[0] = 1
o[0] = 1

for i in range(1,n+1):
    for j in range(1,min(b,i+1)):
        x[i] += o[i-j]
    for j in range(1,min(a,i+1)):
        o[i] += x[i-j]
    for j in range(b+2,min(a,i+1)):
        o[i] += x[i-j]*os[j]
    x[i] %= p
    o[i] %= p

for i in range(b+1,a):
    for j in range(b,i):
        o[n] += xs0[j] * x[n-i]
        o[i]%=p

ans = o[n] + x[n]
ans %= p



beki2 = [1]*5001

for i in range(5000):
    beki2[i+1] = beki2[i]*2
    beki2[i+1] %= p

ans = beki2[n] - ans
ans += p
ans %= p

print(ans)

Solution (Python):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))












n,aa,bb = list(map(int, input().split()))

a = max(aa,bb)
b = min(aa,bb)
p = 1000000007

xs0 = [0]*(n+1)
os0 = [0]*(n+1)

os0[0] = 1

for i in range(b,a-1):
    for j in range(b,i+1):
        xs0[i] += os0[i-j]
        xs0[i] %= p
    for j in range(1,i+1):
        os0[i] += xs0[i-j]
        os0[i] %= p





os = [0]*a

for i in range(b,a-2): 
    for j in range(2,a-i): 
        os[i+j] += xs0[i] * (j-1)

x = [0]*(n+1)
o = [0]*(n+1)

for i in range(b+1,a): 
    for j in range(b,i): 
        o[i] += xs0[j]
        o[i] %= p

x[0] = 1
o[0] = 1

for i in range(1,n+1):
    for j in range(1,min(b,i+1)):
        x[i] += o[i-j]
    for j in range(1,min(a,i+1)):
        o[i] += x[i-j]
    for j in range(b+2,min(a,i+1)):
        o[i] += x[i-j]*os[j]
    x[i] %= p
    o[i] %= p

for i in range(b+1,a):
    for j in range(b,i):
        o[n] += xs0[j] * x[n-i]
        o[i]%=p

ans = o[n] + x[n]
ans %= p



beki2 = [1]*5001

for i in range(5000):
    beki2[i+1] = beki2[i]*2
    beki2[i+1] %= p

ans = beki2[n] - ans
ans += p
ans %= p

print(ans)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, A, B = map(int, read().split())

def solve(N, A, B):
    if A > B:
        A, B = B, A
    if A == 1:
        return pow(2, N, MOD)
    dp1 = np.zeros((N, B), dtype=np.int64)  
    dp2 = np.zeros((N, B), dtype=np.int64)  
    dp1_sum = np.zeros(N, dtype=np.int64)
    ans = 0
    for n in range(N):
        
        if n < A:
            dp1[n, 1] += 1
        else:
            if n + 1 < B:
                dp1[n, n + 1] += 1
        
        if n > 0:
            dp1[n, 1:] += dp1[n - 1, :-1]
        
        dp1[n, 1] += dp1_sum[max(0, n - A):n - 1].sum() % MOD
        
        if n >= A + 1 < B:
            dp1[n, A + 1:B] += dp2[n - A - 1, 0:B - (A + 1)]
        dp1[n] %= MOD
        
        dp1_sum[n] = dp1[n].sum() % MOD
        if (N - n - 1) < A:
            ans += dp1_sum[n]
        else:
            
            M = B - (N - n - 1)
            if M > 0:
                ans += dp1[n, :M].sum() % MOD
        dp2[n] += dp1[n]
        dp2[n, 1:] += dp2[n - 1, :-1]
        dp2[n] %= MOD
    x = pow(2, N, MOD) - ans
    return x % MOD

print(solve(N, A, B))

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, A, B = map(int, read().split())

def solve(N, A, B):
    if A > B:
        A, B = B, A
    if A == 1:
        return pow(2, N, MOD)
    dp1 = np.zeros((N, B), dtype=np.int64)  
    dp2 = np.zeros((N, B), dtype=np.int64)  
    dp1_sum = np.zeros(N, dtype=np.int64)
    ans = 0
    for n in range(N):
        
        if n < A:
            dp1[n, 1] += 1
        else:
            if n + 1 < B:
                dp1[n, n + 1] += 1
        
        if n > 0:
            dp1[n, 1:] += dp1[n - 1, :-1]
        
        dp1[n, 1] += dp1_sum[max(0, n - A):n - 1].sum() % MOD
        
        if n >= A + 1 < B:
            dp1[n, A + 1:B] += dp2[n - A - 1, 0:B - (A + 1)]
        dp1[n] %= MOD
        
        dp1_sum[n] = dp1[n].sum() % MOD
        if (N - n - 1) < A:
            ans += dp1_sum[n]
            ans %= MOD
        else:
            
            M = B - (N - n - 1)
            if M > 0:
                ans += dp1[n, :M].sum() % MOD
        dp2[n] += dp1[n]
        dp2[n, 1:] += dp2[n - 1, :-1]
        dp1[n] %= MOD
        dp2[n] %= MOD
    x = pow(2, N, MOD) - ans
    return x % MOD

print(solve(N, A, B))

Solution (Python):
import math



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

def AddV2(v,w):
    return [v[0]+w[0],v[1]+w[1]]

dir4 = [[1,0],[0,1],[-1,0],[0,-1]]


def clamp(x,y,z):
    return max(y,min(z,x))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            

def Zaatsu(a):
    a.sort()
    now = a[0][0]
    od = 0
    for i in range(n):
        if(now==a[i][0]):
            a[i][0]=od
        else:
            now = a[i][0]
            od+=1
            a[i][0] = od
    
    a.sort(key = lambda x : x[1])
    return a

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

def rl(x):
    return range(len(x))












n,aa,bb = list(map(int, input().split()))

a = max(aa,bb)
b = min(aa,bb)
p = 1000000007

xs0 = [0]*(n+1)
os0 = [0]*(n+1)

os0[0] = 1

for i in range(b,a-1):
    for j in range(b,i+1):
        xs0[i] += os0[i-j]
        xs0[i] %= p
    for j in range(1,i+1):
        os0[i] += xs0[i-j]
        os0[i] %= p





os = [0]*a

for i in range(b,a-2): 
    for j in range(2,a-i): 
        os[i+j] += xs0[i] * (j-1)

x = [0]*(n+1)
o = [0]*(n+1)

for i in range(b+1,a): 
    for j in range(b,i): 
        o[i] += xs0[j]
        o[i] %= p

x[0] = 1
o[0] = 1

for i in range(1,n+1):
    for j in range(1,min(b,i+1)):
        x[i] += o[i-j]
    for j in range(1,min(a,i+1)):
        o[i] += x[i-j]
    for j in range(b+2,min(a,i+1)):
        o[i] += x[i-j]*os[j]
    x[i] %= p
    o[i] %= p

for i in range(b+1,a):
    for j in range(b,i):
        o[n] += xs0[j] * x[n-i]
        o[i]%=p

ans = o[n] + x[n]
ans %= p



beki2 = [1]*5001

for i in range(5000):
    beki2[i+1] = beki2[i]*2
    beki2[i+1] %= p

ans = beki2[n] - ans
ans += p
ans %= p

print(ans)