Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

k = int(input())
s = input()
L = len(s)
def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        # モジュラ逆数の性質
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

mod = 10**9+7
ans = 0
for p in range(L-1,L+k):
  chk = 1
  fact, fact_inv = make_array_for_comb(p,mod)
  chk *= pow(25,p-L+1,mod)
  chk *= comb(p,L-1,mod)
  chk %= mod
  chk *= pow(26,L+k-1-p,mod)
  ans += chk
  ans %= mod
  
print(ans)

### FIXED CODE ###

k = int(input())
s = input()
L = len(s)
mod = 10**9+7

MAX = 2*10**6
fact = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i) % mod

inv = [1]*(MAX+1)
for i in range(2, MAX+1):
    inv[i] = inv[mod % i]*(mod-mod//i) % mod

fact_inv = [1]*(MAX+1)
for i in range(1, MAX+1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

def comb(n, k):
    if n < k:
        return 0
    return fact[n] * fact_inv[n-k] * fact_inv[k] % mod
  
p25 = [1]*(k+1)
p26 = [1]*(k+1)

for i in range(k):
  p25[i+1] = p25[i]*25%mod
  p26[i+1] = p26[i]*26%mod

ans = 0
for p in range(k+1):
  chk = p25[p]*comb(L-1+p,L-1)%mod
  chk *= p26[k-p]%mod
  ans += chk
  ans %= mod
  
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N) :
    a = A[i]
    A[i] = 0
    print(max(A))
    A[i] = a




### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
Max = max(A)
x = A.count(Max)

for i in range(0 ,N) :
    if x >= 2 :
        print(Max)
    elif A[i] == Max :
        A[i] = 0
        print(max(A))
    else : print(Max)
### BUGGY CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

import sys

def main():
    def input(): return sys.stdin.readline().rstrip()
    N = int(input())
    A = [int(input()) for _ in range(N)]
    valiation = list(set(A))
    cnt = 0
    for v in valiation:
        if A.count(v) % 2 != 0:
            cnt += 1
    print(cnt)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    d = {}
    for _ in range(N):
        a = int(input())
        if a not in d:
            d[a] = 1
        else:
            if d[a] == 1:
                d[a] = 0
            else:
                d[a] = 1
    
    cnt = 0
    for v in d.values():
        if v == 1:
            cnt += 1
    print(cnt)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import defaultdict
MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))

for i in range(len(h)-1):
  if h[i] > h[i+1]:
    h[i] = h[i] - 1
  elif h[i] == h[i+1]:
    if h[i] == min(h[i:])-1:
      h[i] = h[i] - 1
if h == sorted(h):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))

for i in reversed(range(1,n)):
  if h[i-1] - h[i] == 1:
    h[i-1] -= 1
  elif h[i-1] - h[i] > 1:
    print('No')
    exit()
print('Yes')
### BUGGY CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
for a in As:
    if a == 1:
        continue
    factors = factorization(a)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]

ans = 0
for a in As:
    ans += lcm//a
    ans %= mod
print(ans%mod)

### FIXED CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)
### BUGGY CODE ###

n,k=map(int,input().split())
A=[]
for i in range(n):
	A.append(int(input()))
C=[]
A.sort()
for i in range(n-k+1):
	B=[]
	for j in range(k):
		B.append(A[i+j])
	C.append(max(B)-min(B))
print(min(C))

### FIXED CODE ###

n,k=map(int,input().split())
A=[]
for i in range(n):
	A.append(int(input()))
C=[]
A.sort()
for i in range(n-k+1):
  C.append(A[i+k-1]-A[i])
print(min(C))
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    #n, m = int(input())
    # 整数複数個
    n, m = map(int, input().split())
    # 整数 N 個 (改行区切り)
    A = [int(input()) for i in range(m)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    Route = [0] * (n+1)
    Route[0] = 1
    for i in range(n):
        if i+1 not in A:
            Route[i+1] = (Route[i] + Route[i+1]) % (10**9 + 7)
            #Route[i+1] %= 10**9 + 7
        if i+2 not in A and i+2 <= n:
            Route[i+2] = (Route[i] + Route[i+2]) % (10**9 + 7)
            #Route[i+2] %= 10**9 + 7

    print(Route[n])
resolve()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    is_safe = [True] * (N+2)
    for a in A:
        is_safe[a+1] = False

    dp = [0] * (N+2)
    dp[1] = 1
    for i in range(2, N+2):
        if is_safe[i]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0

    return dp[N+1]


if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

import heapq

n,m = map(int,input().split())

a = list(map(int,input().split()))

heapq.heapify(a)

for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        x = heapq.heappop(a)
        if(x < c):
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,x)
            break
print(sum(a))

### FIXED CODE ###

import heapq

n,m = map(int,input().split())

a = list(map(int,input().split()))

heapq.heapify(a)

l = [[] for _ in range(m)]

for i in range(m):
    b,c = map(int,input().split())
    l[i] = [c,b]
l.sort(reverse=True)
for i in range(m):
    b,c = l[i][1],l[i][0]
    for j in range(b):
        x = heapq.heappop(a)
        if(x < c):
            heapq.heappush(a,c)
        else:
            heapq.heappush(a,x)
            break
print(sum(a))
### BUGGY CODE ###

#B - Frog 2
#TLE
#

n,k=map(int,input().split())
h = list(map(int,input().split()))
#h[i]は足場[i+1]の高さ

dp = [0]*n

#dp[n-1]まで埋めれば良い

for i in range(1,n):
    c_min=float("inf")
    c_kh=float("inf")
    for j in range(1,k+1):
        #足場i+1までにたどり着くためのコストを考える
        #i~i-k（c[i-1]~c[i-k-1]）の足場からの飛び移り方を考える
        if i-j >= 0:
            c_kh = dp[i-j]+abs(h[i]-h[i-j])
            if c_kh < c_min:
                c_min = c_kh
        dp[i] = c_min
print(dp[n-1])

### FIXED CODE ###

#B - Frog 2
#TLE
#

n,k=map(int,input().split())
h = list(map(int,input().split()))
#h[i]は足場[i+1]の高さ

dp = [0]*n

#dp[n-1]まで埋めれば良い

for i in range(1,n):
    c_min=float("inf")
    c_kh=float("inf")
    for j in range(1,k+1):
        #足場i+1までにたどり着くためのコストを考える
        #i~i-k（c[i-1]~c[i-k-1]）の足場からの飛び移り方を考える
        if i-j >= 0:
            c_kh = dp[i-j]+abs(h[i]-h[i-j])
            if c_kh < c_min:
                c_min = c_kh
        dp[i] = c_min
print(dp[n-1])
### BUGGY CODE ###

# input
N = int(input())
A = []
append = A.append

for i in range(N):
    append(int(input()))

# check
for i in range(N):
    nor_result = [n for j, n in enumerate(A) if j != i]
    if not nor_result:
        continue
    print(max(nor_result))

### FIXED CODE ###

# input
N = int(input())
A = []
append = A.append

for i in range(N):
    append(int(input()))

sort_A = sorted(A, reverse=True)[:2]

# check
for a in A:
    if a == sort_A[0]:
        print(sort_A[1])
    else:
        print(sort_A[0])
### BUGGY CODE ###

from sys import exit

R, G, B, N = map(int, input().split())

count = 0

for r in range(N // R + 1):
	for g in range((N - r * R) // G + 1):
		if N - r * R - g * G < 0:
			break
		if (N - r * R - g * G) % B == 0:
			count += 1

print(count)


### FIXED CODE ###

from sys import exit

R, G, B, N = map(int, input().split())

count = 0

for r in range(N // R + 1):
	for g in range((N - r * R) // G + 1):
		if (N - r * R - g * G) % B == 0:
			count += 1

print(count)
### BUGGY CODE ###

h, n = map(int, input().split())
p = [0] * n
c = [0] * n

inf = 1e9 + 1

for i in range(n):
    pp, cc = map(int, input().split())
    p[i] = pp
    c[i] = cc
    
dp = [inf] * (h + max(p))
dp[0] = 0

for i in range(n):
    for j in range(h):
        dp[j + p[i]] = min(dp[j + p[i]], dp[j] + c[i])
    
print(min(dp[h:]))


### FIXED CODE ###

h, n = map(int, input().split())
p = [0] * n
c = [0] * n

inf = 1e9 + 1

for i in range(n):
    pp, cc = map(int, input().split())
    p[i] = pp
    c[i] = cc
    
dp = [inf] * (h + max(p))
dp[0] = 0

for i in range(n):
    for j in range(h):
        dp[j + p[i]] = min(dp[j + p[i]], dp[j] + c[i])
    
print(min(dp[h:]))
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(a) for a in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]

A.sort(reverse=True)
BC.sort(key=lambda x:x[1], reverse=True)

def bysectsearch(List,num,Left):
    Right = len(List)-1
    while True:
        Midle = (Left+Right)//2
        if List[Left]<=num:
            return Left
        if List[Right]>=num:
            return Right+1
        if Right-Left<=1:
            return Right
        if List[Midle]==num:
            return Midle
        if List[Midle]>num:
            Left = Midle
            continue
        if List[Midle]<num:
            Right = Midle
            continue

Left = 0
for B,C in BC:
    insert_point = bysectsearch(A,C,Left)
    if insert_point == N:
        break
    A = A[:insert_point]+[C]*B+A[insert_point:]
    A = A[:N]
    Left = insert_point + B
    if Left>N-1:
        break
print(sum(A))


### FIXED CODE ###

N,M = map(int,input().split())
A = [int(a) for a in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]

BC.sort(key=lambda x:x[1], reverse=True)

count = 0
Added_list = []
for i in range(M):
    B,C = BC[i]
    Added_list += [C]*B
    count += B
    if count>N:
        Added_list = Added_list[:N]
        break

A += Added_list
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

def warshall(N, ABCs):
    dists = [[100000 * 200 + 1 for _ in range(N)] for __ in range(N)]
    for i in range(N):
        dists[i][i] = 0

    for a, b, c in ABCs:
        dists[a - 1][b - 1] = c
        dists[b - 1][a - 1] = c

    for s in range(N):
        for e in range(N):
            for i in range(N):
                dists[s][e] = min(dists[s][e], dists[s][i] + dists[i][e])
    return dists


from itertools import permutations


def solve(N, M, R, Rs, ABCs):
    dists = warshall(N, ABCs)
    ans = 100000 * 200 + 1 
    for way in permutations(Rs):
        ans = min(ans, sum([dists[i - 1][j - 1] for i, j in zip(way, way[1:])]))

    return ans


if __name__ == "__main__":
    N, M, R = tuple(map(int, input().split(" ")))
    Rs = list(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, R, Rs, ABCs))


### FIXED CODE ###

from itertools import permutations
import heapq

INF = 100000 * 200 * 10

def warshall(N, ABCs):
    dists = [[INF for _ in range(N)] for __ in range(N)]
    for i in range(N):
        dists[i][i] = 0

    for a, b, c in ABCs:
        dists[a - 1][b - 1] = c
        dists[b - 1][a - 1] = c

    for s in range(N):
        for e in range(N):
            for i in range(N):
                dists[s][e] = min(dists[s][e], dists[s][i] + dists[i][e])
    return dists


def dijkstra(s, e, N, ABCs):
    adjlist = [[] for _ in range(N)]
    for a, b, c in ABCs:
        adjlist[a - 1].append((b, c))
        adjlist[b - 1].append((a, c))

    q = [(0, s)]
    while len(q):
        d, i = heapq.heappop(q)
        if i == e:
            return d
        for nexti, nextd in adjlist[i - 1]:
            heapq.heappush(q, (d + nextd, nexti))
    return None


def dense_dijkstra(s, e, N, ABCs):
    distsmap = [[-1 for _ in range(N)] for __ in range(N)]
    for a, b, c in ABCs:
        distsmap[a - 1][b - 1] = c
        distsmap[b - 1][a - 1] = c

    dists = [INF for _ in range(N)]
    visited = [False for _ in range(N)]
    dists[s - 1] = 0

    while True:
        minW, index = min([(dists[i], i) for i in range(N) if not visited[i]])
        visited[index] = True
        if minW == INF:
            return -1
        if index + 1 == e:
            return minW
        for rindex, w in enumerate(distsmap[index]):
            if w == -1:
                continue
            dists[rindex] = min(dists[rindex], minW + w)


def solve(N, M, R, Rs, ABCs):
    dists = [[-1 for _ in range(N)] for __ in range(N)]
    ans = INF
    for way in permutations(Rs):
        tans = 0
        for s, e in zip(way, way[1:]):
            if dists[s - 1][e - 1] == -1:
                d = dense_dijkstra(s, e, N, ABCs)
                dists[s - 1][e - 1] = d
                dists[e - 1][s - 1] = d
            else:
                d = dists[s - 1][e - 1]
            tans += d
        ans = min(ans, tans)

    return ans

if __name__ == "__main__":
    N, M, R = tuple(map(int, input().split(" ")))
    Rs = list(map(int, input().split(" ")))
    ABCs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, R, Rs, ABCs))
### BUGGY CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
happy=[]
for i in range(2**n):
    cnt=0
    ans=0
    for j in range(n):
        if ((i>>j)&1):
            cnt+=a[j]
            ans+=1
    if cnt==x:
        happy.append(ans)
    elif cnt<x:
        if 1<=ans:
            happy.append(ans-1)
        else:
            happy.append(0)
print(max(happy))

### FIXED CODE ###

n,x=map(int,input().split())
a=sorted(list(map(int,input().split())))
cnt=0
ans=0
for i in range(n):
    cnt+=a[i]
    ans+=1
    if x<=cnt:
        break
if x==cnt:
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

l, r = map(int,input().split())
min_val = float('inf')
for i in range(l,r):
  for j in range(l+1, r+1):
    tmp = i*j%2019
    if min_val>tmp:
      min_val = tmp
    if min_val == 0:
      break
print(min_val)

### FIXED CODE ###

l, r = map(int,input().split())
min_val = float('inf')
for i in range(l,r):
  for j in range(l+1, r+1):
    tmp = i*j%2019
    if min_val>tmp:
      min_val = tmp
    if min_val == 0:
      break
  if min_val == 0:
    break
print(min_val)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    H = N // 3
    min_num = -float('inf')
    #dpの初期化
    dp = [[min_num for j in range(H+1)] for i in range(N+1)]
    dp[0][0] = 1
    res = 0
    
    mod=10 ** 9 + 7
    
    for i in range(1, H+1):
        for j in range(3, N+1):
            for k in range(3, j+1):
                if dp[j][i] == min_num:
                    dp[j][i] = dp[j-k][i-1]
                else:
                    if dp[j-k][i-1] != min_num:
                        dp[j][i] += dp[j-k][i-1]

    for num in dp[N]:
        if num != min_num:
            res += (num % mod)
    print(res % mod)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    #dpの初期化
    dp = [0]*(N+1)
    dp[0] = 1
    
    mod=10 ** 9 + 7
    
    for i in range(3, N+1):
        dp[i] = (dp[i-1]+dp[i-3]) % mod
        
    print(dp[N])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys

def solve():
    N = int(input())
    print(0, flush = True)
    a = input()
    basis = -1
    if a == "Vacant": return 0
    elif a == "Male": basis = 0
    else: basis = 1
    low, high = 0, N
    while high - low > 1:
        mid = (low + high) // 2
        print(mid, flush = True)
        a = input()
        if a == "Vacant": break
        else:
            b = (0 if a == "Male" else 1)
            if (mid - basis) % 2 != (a ^ b):
                high = mid
            else:
                low = mid
                basis = b
    else:
        print(low, flush = True)

    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

N = int(input())

print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    reference_state = s
    opposite_state = ("Male" if s == "Female" else "Female") 
    low, high = 0, N
    count = 1
    while count < 20:
        mid = (low + high)//2
        expected_state = (reference_state if mid % 2 == 0 else opposite_state)
        print(mid, flush = True)
        s = input()
        if s == "Vacant":
            break
        else:
            if s == expected_state: low = mid
            else: high = mid
            count += 1