Harryxun/stf_run huggingface dataset:
from collections import deque

# 命令数入力
n = int(input())
# 命令入力
order_list = [input().split() for i in range(n)]


# 双方向連結リスト
doubly_linked_list = deque()

for _ in range(n):
    
    #order = input().split()
    
    if order[0] == "insert":
        doubly_linked_list.appendleft(order[1])
    
    elif order[0] == "delete":
        if order[1] in doubly_linked_list:
            doubly_linked_list.remove(order[1])
    
    elif order[0] =="deleteFirst":
        doubly_linked_list.popleft()
    
    elif order[0] == "deleteLast":
        doubly_linked_list.pop()
        
# 最終結果出力
print(*doubly_linked_list)


### FIXED CODE ###

from collections import deque

# 命令数入力
n = int(input())
# 命令入力
# order_list = [input().split() for i in range(n)]


# 双方向連結リスト
doubly_linked_list = deque()

for _ in range(n):
    
    order = input().split()
    
    if order[0] == "insert":
        doubly_linked_list.appendleft(order[1])
    
    elif order[0] == "delete":
        if order[1] in doubly_linked_list:
            doubly_linked_list.remove(order[1])
    
    elif order[0] =="deleteFirst":
        doubly_linked_list.popleft()
    
    elif order[0] == "deleteLast":
        doubly_linked_list.pop()
        
# 最終結果出力
print(*doubly_linked_list)
import sys
X,K,D = map(int, input().split())
if X < 0: X = abs(X) #Xがマイナスならプラスに変換しておく

if X // D > K:
    X = X - (K * D)
    print(X)
    exit.sys()

if X // D < K:
    if X % D >= abs((X % D)-D):
        print(X % D)
        exit.sys()
    else:
        print(abs((X % D)-D))
        exit.sys()

### FIXED CODE ###

import sys
X,K,D = map(int, input().split())
if X < 0: X = abs(X) #Xがマイナスならプラスに変換しておく

if X // D > K:
    X = X - (K * D)
    print(X)
    sys.exit() #ここはOK

if (X // D) <= K:
    if X % D >= abs((X % D)-D):
        if (K - (X // D)) % 2 == 1:
            print(abs((X % D)-D))
            sys.exit()
        else:
            print(X % D)
            sys.exit()
    else:
        if (K - (X // D)) % 2 == 1:
            print(abs((X % D)-D))
            sys.exit()
        else:
            print(X % D)
            sys.exit()
s = input()
cnt = 0
ans = []
for i in range(0, len(s) - 3):
    j = i
    num = ''
    while j < len(s):
        juhuku = 0
        num += s[j]
        if int(num) % 2019 == 0 and num != '0':
            #print(i, j)
            if j not in ans:
                ans.append(j)
            juhuku = ans.count(i - 1)
            cnt += 1 + juhuku
        j += 1
print(ans)


### FIXED CODE ###

s, w = map(int, input().split())
if s <= w:
    print('unsafe')
else:
    print('safe')
import sys
import numpy as np

i = list(map(int, input().split()))
a = i[0]
b = i[1]
h = i[2]
m = i[3]
time = h*60+m
ths = np.pi/2-(np.pi * time/(60*12))
thl = np.pi/2-(np.pi * m/30.0)
#ths = np.deg2rad(90-h*30.0)
#thl = np.deg2rad(90-m*6.0)
x1 = a*np.cos(ths)
y1 = a*np.sin(ths)
x2 = b*np.cos(thl)
y2 = b*np.sin(thl)
print(np.sqrt((x1-x2)**2+(y1-y2)**2))


### FIXED CODE ###

import sys
import numpy as np
lines = sys.stdin.readlines()
a = int(lines[0].strip())

if a%10 == 3:
  print('bon')
elif a%10 in [0,1,6,8]:
  print('pon')
else:
  print('hon')
import math
a,b=map(int,input().split())
for i in range(1,b+1):
  c=math.factorial(a-b+1)//(math.factorial(i)*math.factorial(a-b+1-i))
  d=math.factorial(b-1)//(math.factorial(i-1)*math.factorial(b-i))
  print((c*d)%1000000007)


### FIXED CODE ###

import math
a,b=map(int,input().split())
for i in range(1,b+1):
  if a-b+1<i:
    print(0)
  else:
    c=math.factorial(a-b+1)//(math.factorial(i)*math.factorial(a-b+1-i))
    d=math.factorial(b-1)//(math.factorial(i-1)*math.factorial(b-i))
    print((c*d)%1000000007)
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (acos, asin, atan, ceil, cos, degrees, factorial, gcd, hypot,
                  log2, pi, radians, sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


def inlist():
    return(list(map(int, input().split())))


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))


def def_value():
    return 0


def ncr(n, r):
    if r > n:
        return 0
    return n*(n-1) // 2


n, m = invr()
res = []
if n == 1:
    res = [0]
elif n == 2:
    res = [1, 0]
elif n == 3:
    res = [1, 0, 0]

f = [0, 0, 0]
out = 1
for _ in range(m):
    si, ci = invr()
    if si == 1 and n > 1 and ci == 0:
        out = -1
        break
    if f[si-1] == 0 or res[si-1] == ci:
        res[si-1] = ci
        f[si-1] = 1
    else:
        out = -1
        break
if out == -1:
    print(-1)
    sys.exit()
if res[0] == 0 and len(res) > 1:
    print(-1)
    sys.exit()
for i in res:
    print(i, end="")


### FIXED CODE ###

import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from itertools import (
    accumulate, combinations, combinations_with_replacement, groupby,
    permutations, product)
from math import (
    acos, asin, atan, ceil, cos, degrees, factorial, hypot, log2, pi, radians,
    sin, sqrt, tan)
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits


def inp():
    return(int(input()))


def inlist():
    return(list(map(int, input().split())))


def instr():
    s = input()
    return(list(s[:len(s)]))


def invr():
    return(map(int, input().split()))


n, m = invr()
res = []
if n == 1:
    res = [0]
elif n == 2:
    res = [1, 0]
elif n == 3:
    res = [1, 0, 0]

f = [0, 0, 0]
out = 1
for _ in range(m):
    si, ci = invr()
    if si == 1 and n > 1 and ci == 0:
        out = -1
        break
    if f[si-1] == 0 or res[si-1] == ci:
        res[si-1] = ci
        f[si-1] = 1
    else:
        out = -1
        break
if out == -1:
    print(-1)

elif res[0] == 0 and len(res) > 1:
    print(-1)
else:
    for i in res:
        print(i, end="")
BIGMOD = 998244353

def modPow(x,n):
    ans = 1
    while n >= 1:
        if bin( n & 1)==bin(1):
            ans = (ans*x) % BIGMOD
        x = x * x % BIGMOD
        n = n>>1
    return ans % BIGMOD

def modFact(N):
    fact = []
    fact.append(1) #0! = 1
    for i in range(1,N+1):
        a = fact[i-1]*i % BIGMOD
        fact.append(a)
    return fact

def modInvFact(fact):
    invFact = []
    for i in range(1,N+2):
        a = modPow(fact[i-1],BIGMOD-2)
        invFact.append(a)
    return invFact

def modPlus(a,b):
    return (a + b) % BIGMOD

def modMinus(a,b):
    if a-b >= 0:
        return (a - b) % BIGMOD
    else:
        return (a - b + BIGMOD)
    
def modMulti(a,b):
    return a * b % BIGMOD

# fact(n),invFact(r),invFact(n-r)
def nCr(fact,invFact,n,r):
    return (fact[n] * invFact[r] * invFact[n-r] ) %BIGMOD

def nPr(fact,invFact,n,r):
    return(fact[n] * invFact[r])%BIGMOD

def fact(num):
    ans = 1
    for i in range(1,num+1):
        ans = ans*i%BIGMOD
    return ans

import collections

N = int(input())
D = list(map(int,input().split()))

S = list(set(D))
S.sort()
if S[0]==0:
    S.pop(0)
ans = 1
before = 0
before_i = 0
c = collections.ounter(D)
for i in S:
    if i == 1:
        before = c[i]
        before_i = i
        continue
    ans = ans*modPow(before,c[i])%BIGMOD
    before = c[i]
    if i - before_i!=1:
        ans = 0
    before_i = i
if D[0] >0:
    print(0)
else:
    print(ans)

### FIXED CODE ###

BIGMOD = 998244353
 
def modPow(x,n):
    ans = 1
    while n >= 1:
        if bin( n & 1)==bin(1):
            ans = (ans*x) % BIGMOD
        x = x * x % BIGMOD
        n = n>>1
    return ans % BIGMOD
 
def modFact(N):
    fact = []
    fact.append(1) #0! = 1
    for i in range(1,N+1):
        a = fact[i-1]*i % BIGMOD
        fact.append(a)
    return fact
 
def modInvFact(fact):
    invFact = []
    for i in range(1,N+2):
        a = modPow(fact[i-1],BIGMOD-2)
        invFact.append(a)
    return invFact
 
def modPlus(a,b):
    return (a + b) % BIGMOD
 
def modMinus(a,b):
    if a-b >= 0:
        return (a - b) % BIGMOD
    else:
        return (a - b + BIGMOD)
    
def modMulti(a,b):
    return a * b % BIGMOD
 
# fact(n),invFact(r),invFact(n-r)
def nCr(fact,invFact,n,r):
    return (fact[n] * invFact[r] * invFact[n-r] ) %BIGMOD
 
def nPr(fact,invFact,n,r):
    return(fact[n] * invFact[r])%BIGMOD
 
def fact(num):
    ans = 1
    for i in range(1,num+1):
        ans = ans*i%BIGMOD
    return ans
 
import collections
 
N = int(input())
D = list(map(int,input().split()))
 
S = list(set(D))
S.sort()
if S[0]==0:
    S.pop(0)
ans = 1
before = 0
before_i = 0
c = collections.Counter(D)
if c[0] > 1:
  ans=0
for i in S:
    if i == 1:
        before = c[i]
        before_i = i
        continue
    ans = ans*modPow(before,c[i])%BIGMOD
    before = c[i]
    if i - before_i!=1:
        ans = 0
    before_i = i
if D[0] >0:
    print(0)
else:
    print(ans)
n=int(input())
p = list(map(int, input().split()))
count=0
for i in range (n-2)
	if p[i]>p[i+1]>p[i+2] or p[i+2]>p[i+1]>p[i]:
    	count=count+1
print(count)

### FIXED CODE ###


n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(n - 2):
	if p[i] < p[i + 1] < p[i + 2] or p[i + 2] < p[i + 1] < p[i]:
		ans += 1
print(ans)
N= map(int, input().split())
A = list(map(int, input().split()))

# if N >= sum(A):
#     print(N-sum(A))
# else:
#     print(-1)
count= [0] * N

for x in A:
    count[x] +=1
for i in range(1,N+1):
    print(count[i])

### FIXED CODE ###

# R = int(input()) 
N= int(input())
A = list(map(int, input().split()))



# if N >= sum(A):
#     print(N-sum(A))
# else:
#     print(-1)
count= [0] * N

for x in A:
    count[x-1] +=1
for i in range(N):
    print(count[i])

# def count_defaultdict(it):
#     counter = collections.defaultdict(int)
#     for x in it:
#         counter[x] += 1
#     return dict(counter)
#El Patron
A = int(input())
B = list(map(int, input().split()))

a = 0
b = 0
ans = 0
while b < A:
    if b < A - 1 and B[b + 1] <= B[b]:
        b += 1
        res = max(res, b - l)
    elif b != l:
        a += 1
    else:
        a += 1
        b += 1
print(res)

### FIXED CODE ###

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

a = 0
b = 0
res = 0
while a < A:
    if a < A - 1 and B[a + 1] <= B[a]:
        a += 1
        res = max(res, a - b)
    elif a != b:
        b += 1
    else:
        b += 1
        a += 1
print(res)
N = map(int, input())
if N%10 == 2 or N%10 == 4 or N%2== 5 or N%10 == 7 or N%10 == 9:
  print("hon")
elif N%10 == 0 or N%10 == 1 or N%10 == 6 or N%10 == 8:
  print("pon")
elif N%10 == 3:
  print("bon")

 

### FIXED CODE ###

N = int(input())
a = N % 10
if a == 2 or a == 4 or a == 5 or a == 7 or a == 9 :
  print ("hon")
elif a == 0 or a == 1 or a == 6 or a == 8 :
  print ("pon")
else :
  print ("bon")
import math
r = input()
m = r ** 2 * 3.14
l = r * 2 * 3.14
print('{:.5f} {:.5f}'.format(m, l))

### FIXED CODE ###

import math
r = float(input())
m = r ** 2 * math.pi
l = r * 2 * math.pi
print('{:.6f} {:.6f}'.format(m, l))
n=int(input())
A=list(map(int,input().split()))
A=[A[i]-i-1 for i in range(n)]
A.sort()
if n%2==1:
    d=A[n//2+1]
    print(sum([abs(A[i]-d) for i in range(n)]))
    exit()
d=(A[n//2-1]+A[n//2])//2
print(sum([abs(A[i]-d) for i in range(n)]))

### FIXED CODE ###

import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n=int(input())
A=list(map(int,input().split()))
SA=[0 for i in range(n)]
for i in range(n):
    SA[i]=A[i]-i-1
SA.sort()

if n%2==0:
    geta=(SA[n//2]+SA[n//2-1])//2
else:
    geta=SA[n//2]
ans=0
for i in range(n):
    ans+= abs(A[i]-(geta+i+1))
print(ans)
import argparse

parser = argparse.ArgumentParser()
parser.add_argument("name")
arg = parser.parse_args()
print(arg.name[:3])

### FIXED CODE ###

import sys

args = input()
print(args[:3])
N = int(input())
A = list(map(int, input().split()))
count=0


def merge(A, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []
    for i in range(n1):
        L.append(A[left + i])
    for i in range(n2):
        R.append(A[mid + i])

    L.append(float("inf"))
    R.append(float("inf"))
    i, j = 0, 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    count += right - left


def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

mergeSort(A,0,N)


print(" ".join(A))
print(count)

### FIXED CODE ###

def merge(a, left, mid, right):
    global count
    n1 = mid - left
    n2 = right - mid
    L = a[left:left + n1] + [SENTINEL]
    R = a[mid:mid + n2] + [SENTINEL]
    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            a[k] = L[i]
            i += 1
        else:
            a[k] = R[j]
            j += 1
    count += right - left
 
def merge_sort(a, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(a, left, mid)
        merge_sort(a, mid, right)
        merge(a, left, mid, right)
 
SENTINEL = 1000000001
n = int(input())
a = list(map(int, input().strip().split()))
count = 0
merge_sort(a, 0, len(a))
print(' '.join(map(str, a)))
print(count)
a = input()
q = int(input())
b = 0
for i in range(q):
    qi=input()
    if qi==str(1):
        b = b+1
    else:
        qi = qi.split()
        if (int(qi[1])+b)%2==1:
            a = qi[2] + a
        else:
            a = a + qi[2]
if b%2==1:
    a = a[::-1]
    print(a)
else:
    print(a)

### FIXED CODE ###

import sys
 
a,b = map(int,input().split())
low = int(min(a//0.08,b//0.1))
high = int(max((a+1)//0.08,(b+1)//0.1))
for i in range(low,high+1):
  if int(i*0.08)==a and int(i*0.1)==b:
    print(i)
    sys.exit()
print(-1)
n = int(input())
A = [int(input()) for i in range(n)]
max = A[1]-A[0]
min = A[0]

for i in range(1,n-2):
    if(min > A[i]):
        for j in range(j,n-1):
            if(max < A[j+1]-A[i]):
                max = A[j+1]-A[i]
print(max)


### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
max = A[1]-A[0]
min = A[0]

for i in range(1,n):
    if(max < A[i]-min):
        max = A[i]-min
    if(min > A[i]):
        min = A[i]

print(max)
import numpy as np
N, D = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(N)]

res = 0
for i in XY:
    if np.sqrt(XY[i][0] ** 2 + XY[i][1] ** 2) <= D:
        res += 1

print(res)


### FIXED CODE ###

import math
N, D = list(map(int, input().split()))
XY = [list(map(int, input().split())) for _ in range(N)]

res = 0
for i in XY:
    if math.sqrt(i[0] ** 2 + i[1] ** 2) <= D:
        res += 1

print(res)
orders = {
    'North': (2, 6, 3, 4, 1, 5),
    'East': (4, 2, 1, 6, 5, 3),
    'West': (3, 2, 6, 1, 5, 4),
    'South': (5, 1, 3, 4, 6, 2),
    'Right': (1, 3, 5, 2, 4, 6),
    'Left': (1, 4, 2, 5, 3, 6)
}

while True:
    n = int(input())
    if not n:
        break
    dice = list(range(1, 7))
    top = 1

    while n:
        new_dice = [dice[s - 1] for s in orders[input()]]
        dice = new_dice
        top += dice[0]
        n -= 1
    print(top)

### FIXED CODE ###

orders = {
    'North': (2, 6, 3, 4, 1, 5),
    'East': (4, 2, 1, 6, 5, 3),
    'West': (3, 2, 6, 1, 5, 4),
    'South': (5, 1, 3, 4, 6, 2),
    'Right': (1, 3, 5, 2, 4, 6),
    'Left': (1, 4, 2, 5, 3, 6)
}

while True:
    n = int(input())
    if not n:
        break
    dice = list(range(1, 7))
    top = 1

    while n:
        dice = [dice[s - 1] for s in orders[input().strip()]]
        top += dice[0]
        n -= 1
    print(top)
def calc(n, p):
    count = 0
    for i in range(1, n-1):
        if p[i-1] < p[i] and p[i] < p[i+1]:
            count += 1
            continue
        if p[i-1] > p[i] and p[i] > p[i+1]:
            count += 1
            continue

    return count
print(calc(input(), list(input().split())))

### FIXED CODE ###

def calc(n, p):
    count = 0
    for i in range(1, n-1):
        if p[i-1] < p[i] and p[i] < p[i+1]:
            count += 1
            continue
        if p[i-1] > p[i] and p[i] > p[i+1]:
            count += 1
            continue
    return count
print(calc(int(input()), [int(a) for a in input().split()]))
N, M = map(int, input().split())

def primefactorize(n):
    fct = []  # return [[p1, power1], [p2, power2], ...]
    p, power = 2, 0
    while p * p <= n:
        while n % p == 0:
            n = n // p
            power += 1
        if power > 0:
            fct.append([p, power])
        if p == 2:
            p += 1
        else:
            p += 2
        power = 0
    if n > 1:
        fct.append([n, 1])
    return fct

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

fct = primefactorize(M)
factors = []
for div in divisorize(fct):
    factors.append(num(div))

factors.sort()
cd = 0
k = M/N
for x in factors:
    if x <= k:
        cd = max(cd, x)
print(cd)

### FIXED CODE ###

N, M = map(int, input().split())

def primefactorize(n):
    fct = []  # return [[p1, power1], [p2, power2], ...]
    p, power = 2, 0
    while p * p <= n:
        while n % p == 0:
            n = n // p
            power += 1
        if power > 0:
            fct.append([p, power])
        if p == 2:
            p += 1
        else:
            p += 2
        power = 0
    if n > 1:
        fct.append([n, 1])
    return fct

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

if M != 1:
    fct = primefactorize(M)
    factors = []
    for div in divisorize(fct):
        factors.append(num(div))
else:
    factors = [1]
factors.sort()
k = M//N
L = [x for x in factors if x <= k]
print(max(L))
N, L = map(int, input())

t = map(lambda i: L + i, range(N))

targ = sum(t)
res = 0
for c in t:
    now = targ - c
    if m > abs(targ - now):
        m = abs(targ - now)
        res = now

print(res)

### FIXED CODE ###


N, L = map(int, input().split())

t = list(map(lambda i: L + i, range(N)))

targ = sum(t)
m = 10000000000000
res = 0
for c in t:
    now = targ - c
    if m > abs(targ - now):
        m = abs(targ - now)
        res = now

print(res)
r = int(input())
print(2, 2)

### FIXED CODE ###

import math
r = float(input())
print(r * r * math.pi, 2 * r * math.pi)
# import module
import sys
import math
import numpy as np

S = input()

if S.find(A) != -1 and S.find("B") != 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# import module
import sys
import math
import numpy as np

S = input()

if S.find("A") != -1 and S.find("B") != -1:
    print("Yes")
else:
    print("No")
X,N=map(int,input().split())
P=list(map(int,input().split()))
 
if N==0:
    print(X)
else:
    if X<min(P):
        ans=X
        print(ans)
    
    elif X in range(min(P),max(P)+1):
        #大した大きい数じゃないので全探索すればいい
        ans_len=200 #ひとまずの仮定
        for i in range(min(P),max(P)+1):
            if i in P:
                continue
            else:
                l=abs(X-i)
                if l < ans_len:
                    ans_len=l
                    ans=i
        print(ans)
                
    else:
        ans=X
        print(ans)

### FIXED CODE ###

X,N=map(int,input().split())
P=list(map(int,input().split()))

if N==0:
    print(X)
else:
    if X<min(P):
        ans=X
        print(ans)
    
    elif X in range(min(P),max(P)+1):
        #大した大きい数じゃないので全探索すればいい
        ans_len=200 #ひとまずの仮定
        for i in range(250):
            if i in P:
                continue
            else:
                l=abs(X-i)
                if l < ans_len:
                    ans_len=l
                    ans=i
        print(ans)
                
    else:
        ans=X
        print(ans)
s = int(input())

from scipy.special import comb

ans = 0
for i in range(x):
    Box = i + 1
    Nokori = s - 3 * Box
    ans_ = comb(Nokori + Box - 1, Nokori, exact=True) % (10 ** 9 + 7)
    ans += ans_
    #ans = ans % (10 ** 9 + 7)
print(ans % (10 ** 9 + 7))

### FIXED CODE ###

s = int(input())

x = s // 3

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

ans = 0
for i in range(x):
    Box = i + 1
    Nokori = s - 3 * Box
    ans_ = cmb(Nokori + Box - 1, Box - 1) 
    ans += ans_
print(ans % (10 ** 9 + 7))