Harryxun/stf_run huggingface dataset:
a=[]
n=int(input())
for i in range(3,n+1):
    if i%3==0 or i%10==3:
        a.append(i)
print(' '+*a)

### FIXED CODE ###

n=int(input())
c,i=0,1
while i <= n:
    if c==0:
        x=i
        if x%3==0:
            print(' '+str(i), end='')
            i+=1
            continue
    c=0
    if x%10==3:
        print(' '+str(i), end='')
        i+=1
        continue
    x//=10
    if x == 0:
        i+=1
        continue
    else:
        c=1
print()
import sys
import math

def isExponential(i : int) -> bool:
    for j in range(math.sqrt(i)):
        devidend = i
        devisor = j
        while 1:
            if devidend % devisor != 0:
                break
            else:
                if devidend == devisor:
                    return 1
                else:
                    devidend //= devisor
    return 0
x = int(input())
for i in range(x,0,-1):
    if isExponential(i):
        print(i)
        break

### FIXED CODE ###

import sys
import math

def isExponential(i : int) -> bool:
    #math.ceil(math.sqrt(i))+1
    for j in range(2,i):       
        devidend = i
        devisor = j
        #print(devidend,devisor,"inFor") 
        while 1:
            #print(devidend,devisor,"inWhile")
            if devidend % devisor != 0:
                break
            else:
                if devidend == devisor:
                    return True
                else:
                    devidend //= devisor
    return False

x = int(input())
if x == 1:
    print(1)
for i in range(x,0,-1):
    if isExponential(i) == True:
        print(i)
        #print("wtf")
        break
x = long( input() )
print( x*x*x)


### FIXED CODE ###

x = int( input() )
print( x*x*x)
N=int(raw_input())
S=raw_input()

op=S.count('(')
cl=S.count(')')

if op>cl:
    r=S+')'*(op-cl)
elif cl>op:
    r='('*(cl-op)+S

print r

### FIXED CODE ###

N=int(raw_input())
S=raw_input()

s=list(S)

i=0
j=0
while i<N and j<N:
    #print i,s
    if s[i]=='(':
        j=i
        while j<N:
            #print i,j
            if s[j]==')':
                s[i]='x'
                s[j]='x'
                #print (i,j),s
                i+=1
                break
            else:
                j+=1
    else:
        i+=1

op=s.count(')')
cl=s.count('(')

print '('*op+S+')'*cl
import math

def factorization(n):
    arr = []
    tmp = n
    for div in range(2, int(math.sqrt(n))+1):
        if tmp % div == 0:
            cnt = 0
            while tmp % div == 0:
                cnt += 1
                tmp //= div
            arr.append([div, cnt])

    if tmp != 1:
        arr.append([tmp, 1])

    if len(arr) == 0:
        arr.append([n, 1])

    return arr

if __name__ == '__main__':
    A, B = map(int, input().split())
    gcd = math.gcd(A, B)
    if gcd == 1:
        print(1)
        exit()
    facts = factorization(gcd)
    print(len(facts) + 1)

### FIXED CODE ###

import math
import fractions
gcd = math.gcd if hasattr(math, "gcd") else fractions.gcd

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

def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

g = gcd(A, B)

print(len(set(factorize(g)))+1)
n,k,q=map(int,input().split()) 

for a in range(q):
    score[int(input())-1] +=1

for j in range(n):
    if score[j-1] > 0:
        print('Yes')
    else:
        print('No')
        
        

### FIXED CODE ###

n,k,q=map(int,input().split()) 
score=[k-q]*(n)


for a in range(q):
    score[int(input())-1] +=1

for j in range(n):
    if score[j] > 0:
        print('Yes')
    else:
        print('No')
n,m = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]

num = 0
ct = 0
while num <= m and ct <= len(l):
    ct +=1
    num += l[ct-1]
    
print(ct)

### FIXED CODE ###

n,m = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]

num = 0
ans = 1
for i in l:
    num += i
    if num > m:
        break
    else:
        ans +=1
    
print(ans)
a, b = map(int, input().split())
array = list(map(int, input().split()))
impossible = "IMPOSSIBLE"
possible = "POSSIBLE"

if a == 1:
    if b == array[0]:
        print(possible)
    else:
        print(impossible)
    exit(0)

array = list(set(array))
array.sort()

btw = [v1 - v2 for v1, v2 in zip(array[1:], array[0:])]
n = sorted(btw)[0]

same = len(set(btw)) == 1 or all([v % n == 0 for v in btw])

if b in array:
    print(possible)
elif array[-1] < b:
    print(impossible)
elif same and (b - array[0]) % n == 0:
    print(possible)
else:
    print(impossible)


### FIXED CODE ###

a, b = map(int, input().split())
array = list(map(int, input().split()))
impossible = "IMPOSSIBLE"
possible = "POSSIBLE"

array = list(set(array))

if len(array) == 1:
    if b == array[0]:
        print(possible)
    else:
        print(impossible)
    exit(0)

array.sort()

btw = [v1 - v2 for v1, v2 in zip(array[1:], array[0:])]
n = sorted(btw)[0]

same = len(set(btw)) == 1 or all([v % n == 0 for v in btw])

if b in array:
    print(possible)
elif array[-1] < b:
    print(impossible)
elif same and (b - array[0]) % n == 0:
    print(possible)
else:
    print(impossible)
A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0

for i in range(A+1);
 for j in range(B+1);
  reX = X - A*i - B*j;
  if 0<= reX <= X
  count++;

print(count)


### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

count = 0

for i in range(A+1):
        for j in range(B+1):
                reX = (X - 500*i - 100*j)//50
                if 0 <= reX <= C:
                        count+=1
   
   
print(count)
N,X=map(int,input().split())
L=list(map(int,input().split()))

d=0
count=1
for l in L
 d=d+1
  if X>=d:
  count +=1
print(count)


### FIXED CODE ###

X,A = map(int,input().split())
L = list(map(int,input().split()))
 
d = 0
count = 1
for l in L:
    d = d + l
    if A>= d:
        count += 1
        
    
print(count)
import math
import sys
input = sys.stdin.readline


def dfs(v, x, G, X, visited, ans):
    visited[v] = True
    ans[v] = x

    for nv in G[v]:
        if visited[nv]:
            continue
        dfs(nv, x+X[nv], G, X, visited, ans)


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    X = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        X[p-1] += x
    
    visited = [False]*N
    ans = [0]*N
    dfs(0, X[0], G, X, visited, ans)
    print(' '.join(list(map(str, ans))))
    


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(300000)


def dfs(v, x, G, X, visited, ans):
    visited[v] = True
    ans[v] = x
    # print(visited)

    for nv in G[v]:
        if visited[nv]:
            continue
        dfs(nv, x+X[nv], G, X, visited, ans)


def main():
    N, Q = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    X = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        X[p-1] += x
    # print(G)
    # print(X)
    
    visited = [False]*N
    ans = [0]*N
    dfs(0, X[0], G, X, visited, ans)
    print(' '.join(list(map(str, ans))))
    

if __name__ == '__main__':
    main()
# D - Redistribution
S = int(input())
MOD = 10**9+7

# dp[i]: 3 以上の数字で i を作る組み合わせ
dp = [0]*(S+1)

# 初期条件
dp[3],dp[4],dp[5] = 1,1,1


# i を作る組合わせ
for i in range(6,S+1):
    dp[i] = dp[i-2] + dp[i-3] + dp[i-4]

ans = (dp[S])%MOD
print(ans)

### FIXED CODE ###

# D - Redistribution
S = int(input())
MOD = 10**9+7

# dp[i]: 3 以上の数字で i を作る組み合わせ
dp = [0]*(S+1)

if S <= 2:
    print(0)
elif S <= 5:
    print(1)
else:
    # 初期条件
    dp[3],dp[4],dp[5] = 1,1,1

    # i を作る組合わせ
    for i in range(6,S+1):
        dp[i] = dp[i-2] + dp[i-3] + dp[i-4]

    ans = (dp[S])%MOD
    print(ans)
a = int(input())
b = int(input())
if a*b % 2 == 0:
    print('Even')
else:
    print('Odd')

### FIXED CODE ###

a,b = [int(i) for i in input().split()]
if a*b % 2 == 0:
    print('Even')
else:
    print('Odd')
a = str(input())
if a.isupper() == True:
    print(A)
else:
    print(a)


### FIXED CODE ###

a = str(input())
if a.isupper() == True:
    print("A")
else:
    print("a")
letters = list(input())
true_false = 1
for letter in letters:
  if letters.count(letter) == 2:
    true_false　*= 1
  else:
    true_false *= 0
print(["No","Yes"][true_false])


### FIXED CODE ###

letters = list(input())
x = 1
for letter in letters:
        if letters.count(letter) == 2:
            x *= 1
        else:
            x *= 0
print(["No","Yes"][x])
S = list(input())

for i in range(len(S) - 1):
    if S[i] == "h" and S[i + 1] == "i" and S[i + 2] != "i":
        print("Yes")
        exit()

print("No")

### FIXED CODE ###

S = input()

if len(S) % 2 != 0:
    print("No")
    exit()

if len(S) == 2 and S == "hi":
    print("Yes")
    exit()
elif len(S) == 4 and S == "hihi":
    print("Yes")
    exit()
elif len(S) == 6 and S == "hihihi":
    print("Yes")
    exit()
elif len(S) == 8 and S == "hihihihi":
    print("Yes")
    exit()
elif len(S) == 10 and S == "hihihihihi":
    print("Yes")
    exit()

print("No")
# ABC044
N, A = map(int, input().split())
X = list(map(int, input().split()))

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N

dp = [[[0] * (N*A+5) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(N):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

ans = 0
for k in range(1, N+1):
    ans += dp[-1][k][k*A]

print(ans)

### FIXED CODE ###

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

# 2 ** 50 -> 全探索は厳しい -> DP
# dp[i][k][wa] = i枚まで見て、k枚選んだ時の合計値がwaとなるときの選び方の合計
# max wa = max(X) * N
max_wa = max(X) * N
dp = [[[0] * (max(X) * (N+1)) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for k in range(i+1):
        for wa in range(max_wa):
            # 選ぶとき
            dp[i+1][k+1][wa+X[i]] += dp[i][k][wa]
            # 選ばないとき
            dp[i+1][k][wa] += dp[i][k][wa]

ans = 0
for k in range(1, N+1):
    if k * A > max_wa:
        break
    ans += dp[-1][k][k*A]

print(ans)
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = ind + l[1] -1 
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

CB = []
for i in range(M):
    b, c = map(int, input().split())
    CB.append([c, b])
CB.sort(reverse=True)
CBCB = [CB[0]]
for i in range(1, M):
    if CB[i][0]==CB[i-1][0]:
        CBCB[-1][1]+= CB[i][1]
    else:
        CBCB.append(CB[i])

ind = 0
ans=0
for l in CBCB:
    if A[ind]>l[0]: # 打ち切り
        break
    elif A[min(ind+l[1]-1, N-1)]<l[0]: #すべて置き換え
        if ind+l[1]>N-1:
            ans+=l[0]*(N-ind)
            ind = N
            break
        else:
            ans+=l[0]*l[1]
            ind+=l[1]
    else:
        sm = ind-1
        la = min(ind + l[1] -1 , N-1)
        while sm+1<la:
            md = (sm+la)//2
            if A[md]>=l[0]:
                la = md
            else:
                sm = md
        ans += l[0]*(sm-ind+1)
        ind = sm+1
        break
        
for i in range(ind, N):
    ans+=A[i]
print(ans)
N=int(input())
A=[int(input()) for i in range(N)]
B=[0]*N
for i in range(N):
    if A[i]>0:
        if A[i]%2==0:
            B[i]=2
        else:
            B[i]=1
L=[0,2,1,2,0]
dp=[[10**9]*5 for i in range(N+1)]
for k in range(5):
    dp[0][k]=0
for i in range(1,N+1):
    for k in range(5):
        for k1 in range(k+1):
            if 1<=k<=3:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+abs(L[k]-B[i-1]))
            else:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+A[i-1])
ans=10**9
#print(B)
#print(dp)
for a in range(5):
    ans=min(ans,dp[N][a])
print(ans)v

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
B=[0]*N
for i in range(N):
    if A[i]>0:
        if A[i]%2==0:
            B[i]=2
        else:
            B[i]=1
L=[0,2,1,2,0]
dp=[[10**9]*5 for i in range(N+1)]
for k in range(5):
    dp[0][k]=0
for i in range(1,N+1):
    for k in range(5):
        for k1 in range(k+1):
            if 1<=k<=3:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+abs(L[k]-B[i-1]))
            else:
                dp[i][k]=min(dp[i][k],dp[i-1][k1]+A[i-1])
ans=10**9
#print(B)
#print(dp)
for a in range(5):
    ans=min(ans,dp[N][a])
print(ans)
N,K=map(int,input().split())
x=998244353
S=[]
for i in range(K):
    l,r=map(int,input().split())
    for j in range(l,r+1):
      S.append(j)
S=list(set(S))
dp=[0 for i in range(N)]
for i in range(len(S)):
    dp[S[i]]=1
for i in range(N):
    for j in range(len(S)):
        if(i-S[j]>0):
            dp[i]+=dp[i-S[j]]
            dp[i]=dp[i]%x
print(dp[-1])

### FIXED CODE ###

N,K=map(int,input().split())
x=998244353
dp=[0 for i in range(N)]
sdp=[0 for i in range(N)]
L=[]
R=[]
dp[0]=1
sdp[0]=1
for i in range(K):
    l,r=map(int,input().split())
    L.append(l)
    R.append(r) 
for i in range(1,N):
    for j in range(K):
        dp[i]+=(sdp[max(i-L[j],-1)]-sdp[max(i-R[j]-1,-1)])
        dp[i]%=x
    sdp[i]=(sdp[i-1]+dp[i])%x
print(dp[-1]%x)
A = int(input())
B = int(input())
C = int(input())
X = int(input())

ans = 0

c500 = X // 500

for i in range(c500 + 1):
    c100 = (X - i*500) / 100
    if c100 > B:
        continue
    for j in range(c100+1):
        c50 = (X - i*500 - j*100)/50
        if c50 <= C:
           ans += 1

print(ans)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

ans = 0

c500 = X // 500

if c500 > A:
    c500 = A

for i in range(c500 + 1):
    c100 = (X - i*500) // 100
    if c100 > B:
        c100 = B
    for j in range(c100 + 1):
        c50 = (X - i*500 - j*100) // 50
        if c50 <= C:
           ans += 1

print(ans)
N = int(input())

p = []

for i in raneg(N):
    P = int(input())
    p.append(P)


new_p = sorted(p, reverse=True)

p_max = (new_p[0]/2)

NEW_p = (new_p[1:len(new_p)])

NEWP_SUM = sum(NEW_p)

print(int((p_max) + (NEWP_SUM)))

### FIXED CODE ###

N = int(input())
p = []
for _ in range(N):
    p.append(int(input()))
p = sorted(p)
p[-1] = p[-1]//2
print(sum(p))
n = int(input())
a = list(map(int, input().split()))
out = 1
for i in range(n):
    out = out * a[i]
    if out == 0:
        print(out)
        quit()
    elif out >＝ 10**18:
        print(-1)
        quit()
print(out)
         

### FIXED CODE ###

# -*- coding: utf-8 -*-
from decimal import Decimal
# input
n = int(input())
a = list(map(int, input().split()))
out = 1
if 0 in a:
    print(0)
    quit()
for i in range(n):
    out = Decimal(out * a[i])
    if out > Decimal(10**18):
        print(-1)
        quit()
print(out)
n = int(input())
if n % 2 = 0:
  ans = n // 2
if n % 2 = 1:
  ans = n //2 + 1
print(ans)

### FIXED CODE ###

n = int(input())
if n % 2 == 0:
  ans = n // 2
else:
  ans = n // 2 + 1
print(ans)
N, K = input().split()
P = list(map(int,input().split()))
 
P.sort()
 
total=0
for i in range(K+1):
  total=total+P[i]
 
print(total)

### FIXED CODE ###

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

P.sort()
 
total=0

for i in range(int(K)):
    total=total+P[i]
 
print(total)
# 締切の早いものから順番に見ていくのが最適戦略
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
X = sorted(X, key=lambda x: x[1])  # B (締切の早い順にソート)

res = 0
for i in range(N):
    res += A[i]
    if res > B[i]:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

N = int(input())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[1])
a = [0] * N
a[0] = X[0][0]
for i in range(1, N):
	a[i] = a[i - 1] + X[i][0]
for j in range(N):
	if a[j] > X[j][1]:
		print("No")
		exit()
print("Yes")
import numpy as np
import math
n, m = map(int, input().split())
#a = list(map(int, input().split()))
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    MAX = heapq.heappop(a)  # −１かけたリストのMin　＞Max
    heapq.heappush(a, (-1) * (-MAX // 2))

ans = (sum(a)) * (-1)  # そのままリストでOK
print(ans)

### FIXED CODE ###

#import numpy as np
#import math
import heapq

n, m = map(int, input().split())
#a = list(map(int, input().split()))
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)  # aを優先度付きキューに

for _ in range(m):
    MAX = heapq.heappop(a)  # −１かけたリストのMin　＞Max
    heapq.heappush(a, (-1) * (-MAX // 2))

ans = (sum(a)) * (-1)  # そのままリストでOK
print(ans)
import heapq

def dijkstra(ad_lst, n, s, t):
    costs = [float('inf') for i in range(n+1)]
    costs[s] = 0
    prevs = [-1 for _ in range(n+1)]
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            alt = costs[u] + c
            if alt < costs[v]:
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

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

route_y = {i: [] for i in range(n+1)}
route_s = {i: [] for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u].append([v,a])
    route_y[v].append([u,a])
    route_s[u].append([v,b])
    route_s[v].append([u,b])

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
cost_ys = [[y+s, i] for y, s in zip(cost_y, cost_s)]

cost_ys.sort()
yen = 10**15
k = 0
for i in range(n):
    while cost_ys[k][1]<=i: k+=1
    print(yen-cost_ys[k][0])
# inf = float('inf')
# result = [inf for _ in range(n+1)]
# min_cost = result[-1]
# for i in range(n, 0, -1):
#     if min_cost > cost_ys[i]:
#         min_cost = cost_ys[i]
#     result[i] = min_cost
# yen = 10**15
# for i in range(1, n+1):
#     print(yen - result[i])


### FIXED CODE ###

import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

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

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

s = ri()
dp = [1]*(s+1)
for i in range(3):
    dp[i]=0
dp[3]=1
#[0,0,1,1,1,2,3,]
#a[i] = a[i-3]+...+a[0]
#     = a[i-3]+a[i-1]
for i in range(4,s+1):#3-7
    dp[i] = dp[i-3]+dp[i-1]

print(dp[s]%MOD)

### FIXED CODE ###

import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

s = ri()
dp = [1]*max(4,(s+1))
for i in range(3):
    dp[i]=0
dp[3]=1
#[0,0,1,1,1,2,3,]
#a[i] = a[i-3]+...+a[0]
#     = a[i-3]+a[i-1]
for i in range(4,s+1):#3-7
    dp[i] = dp[i-3]+dp[i-1]

print(dp[s]%MOD)
import heapq

a,b,c,k=map(int,input())
arr1=list(map(int,input().split()))
arr1=sorted(arr1,reverse=True)
arr2=list(map(int,input().split()))
arr2=sorted(arr2,reverse=True)
arr3=list(map(int,input().split()))
arr3=sorted(arr3,reverse=True)
heap=[]
heapq.heappush(heap,(-(arr1[0]+arr2[0]+arr3[0]),0,0,0))
s={(0,0,0)}
for _ in range(k):
  v,i,j,k=heapq.heappop(heap)
  if i+1<a and (i+1,j,k) not in s:
    s.add((i+1,j,k))
    heapq.heappush(heap,(-(arr1[i+1]+arr2[j]+arr3[k]),i+1,j,k))
  if j+1<b and (i,j+1,k) not in s:
    s.add((i,j+1,k))
    heapq.heappush(heap,(-(arr1[i]+arr2[j+1]+arr3[k]),i,j+1,k))
  if k+1<c and (i,j,k+1) not in s:
    s.add((i,j,k+1))
    heapq.heappush(heap,(-(arr1[i]+arr2[j]+arr3[k+1]),i,j,k+1))
  print(-v)

### FIXED CODE ###

import heapq

a,b,c,k=map(int,input().split())
arr1=list(map(int,input().split()))
arr1=sorted(arr1,reverse=True)
arr2=list(map(int,input().split()))
arr2=sorted(arr2,reverse=True)
arr3=list(map(int,input().split()))
arr3=sorted(arr3,reverse=True)
heap=[]
heapq.heappush(heap,(-(arr1[0]+arr2[0]+arr3[0]),0,0,0))
s={(0,0,0)}
for _ in range(k):
  v,i,j,k=heapq.heappop(heap)
  if i+1<a and (i+1,j,k) not in s:
    s.add((i+1,j,k))
    heapq.heappush(heap,(-(arr1[i+1]+arr2[j]+arr3[k]),i+1,j,k))
  if j+1<b and (i,j+1,k) not in s:
    s.add((i,j+1,k))
    heapq.heappush(heap,(-(arr1[i]+arr2[j+1]+arr3[k]),i,j+1,k))
  if k+1<c and (i,j,k+1) not in s:
    s.add((i,j,k+1))
    heapq.heappush(heap,(-(arr1[i]+arr2[j]+arr3[k+1]),i,j,k+1))
  print(-v)
a,b = int(input())
z =[]

c = 0
for i in 999:
  c +=i
  z.append(c)

w =max(a,b)-min(a,b)
if (w==z[i+1]-z[i]):
  print(z[i]-a)

### FIXED CODE ###

a, b = map(int, input().split())
c = b - a
lb = 0
for i in range(1, c + 1):
  lb += i
print(lb - b)