Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
dp = [[0,-1] for i in range(n+1)]

for i in range(n):
    a = l[i].index(max(l[i]))
    if dp[i][1] == a:
        b = l[i].index(min(l[i]))
        dp[i+1][0],dp[i+1][1] = dp[i][0]+l[i][3-a-b],3-a-b
    else:
        dp[i+1][0],dp[i+1][1] = dp[i][0]+l[i][a],a
    
print(dp[n][0])
        
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
dp = [[0]*3 for i in range(n+1)]

for i in range(n):
    dp[i+1][0] = max(dp[i][1],dp[i][2])+l[i][0]
    dp[i+1][1] = max(dp[i][0],dp[i][2])+l[i][1]
    dp[i+1][2] = max(dp[i][1],dp[i][0])+l[i][2]
    
print(max(dp[n]))
import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7

if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()

A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]

ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]

if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)

B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD

C1=A[0:K]
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))

ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD

if Bp[-1]*B2[-1]-Bm[0]*B2[0]:
  print(ansB)
elese print(ansC)

#print(max(ansB,ansC))

### FIXED CODE ###

import numpy as np
N,K=map(int, input().split())
A =list(map(int,input().split()))
MOD = 10 ** 9 + 7
if N==K:
  ans0 = 1
  for a in A[0:N]:
    ans0 *= a
    ans0 %= MOD
  print(ans0)
  exit()
A=sorted(A)  
if (K%2==1 and A[-1]<0):
  ans1 = 1
  for a in A[N-K:N]:
    ans1 *= a
    ans1 %= MOD
  print(ans1)
  exit()
 
A=sorted(A, key=lambda x:abs(x), reverse=True)
AA=[np.sign(i) for i in A]
 
ansA = 1
for a in A[0:K]:
  ansA *= a
  ansA %= MOD
ansAA = AA[0:K].count(-1)%2
if ansA==0 or ansAA==0:
  print(ansA)
  exit()

while ansA>0:
  ansA-=MOD

B1=A[0:K]
C1=A[0:K]
B2=sorted(A[K:N])
Bp=[i for i in A[0:K] if i>0]
Bm=[i for i in A[0:K] if i<0]
 
if B2[0]>0:B2.insert(0,0)
if B2[-1]<0:B2.insert(-1,0)
if not Bp:Bp.insert(0,B1[-1])
if not Bm:Bm.insert(0,B1[0])
  
#print(Bp,Bm,B2)
#print(Bp[-1],B2[0])
B1.remove(Bp[-1])
B1.append(min(B2[0],0))
#print(B1)
ansB = 1
for a in B1[0:K]:
  ansB *= a
  ansB %= MOD
#print(Bm[-1],B2[-1])
C1.remove(Bm[-1])
C1.append(max(B2[-1],0))
 
ansC = 1
for a in C1[0:K]:
  ansC *= a
  ansC %= MOD
#print(B1,C1)
#print(ansB,ansC)
BB1=[np.sign(i) for i in B1]
ansBB1 = BB1[0:K].count(-1)%2
BB2=[np.sign(i) for i in C1]
ansBB2 = BB2[0:K].count(-1)%2
#print(ansBB1,ansBB2)
if ansBB1==1:
  print(ansC)
  exit()
if ansBB2==1:
  print(ansB)
  exit()
#print(B2[0]/Bp[-1],B2[-1]/Bm[-1])
#print(Bp[-1]*B2[-1],Bm[0]*B2[0])

#print(abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0]))
#print(ansB,ansC)
if abs(Bp[-1]*B2[-1])-abs(Bm[-1]*B2[0])>=0:
  print(ansC)
else: print(ansB)
def f(x,y):
	list=[0]
	for z in y:
		for i in range(len(list)-1,-1,-1):
			tmp=x.find(z,list[i])+1
			if tmp:
				if i+1 < len(list):
					list[i+1]=min(list[i+1],tmp)
				else:
					list.append(tmp)
	return len(list)-1
 
n=int(input())
for i in range(q):
	x=input()
	y=input()
	print(f(x,y))


### FIXED CODE ###


def f(x,y):
	list=[0]
	for z in y:
		for i in range(len(list)-1,-1,-1):
			tmp=x.find(z,list[i])+1
			if tmp:
				if i+1 < len(list):
					list[i+1]=min(list[i+1],tmp)
				else:
					list.append(tmp)
	return len(list)-1
 
n=int(input())
for i in range(n):
	x=input()
	y=input()
	print(f(x,y))
n,k = map(int,imput().split())
ans = [1] * n

for i in range(k):
  d = int(input())
  for j in list(map(int,input().split())):
    ans[j-1] = 0

print(ans.count(1))

### FIXED CODE ###

n,k = map(int,input().split())
ans = [1]*n

for i in range(k):
  d = int(input())
  for j in list(map(int,input().split())):
    ans[j-1] = 0

print(ans.count(1))
H,N=map(int,input().split())
AB=[]
for _ in range(N):
    a,b=map(int,input().split())
    AB.append((a,b))
dp=[0]*(H+1)
for i in range(1,H+1):
    for a,b in AB:
        if dp[i]==0:
            dp[i]=dp[max(i-a,0)]+b
        else:
            dp[i]=min(dp[i],dp[i-a]+b)
print(dp[H])

### FIXED CODE ###

H,N=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N)]
x=max(a for a,b in ab)
dp=[0]*(H+x)
for i in range (1,H+x):
    dp[i]=min(dp[i-a]+b for a,b in ab)
print(dp[H])
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    a, b = LI()
    gcd = math.gcd(a, b)
    print(a*b//gcd)
        

main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    a, b = LI()
    gcd = fractions.gcd(a, b)
    print(a*b//gcd)

main()
from math import pi
r=float(int, import())
print(pi*r*r, 2*pi*r)

### FIXED CODE ###

from math import pi
r=float(input())
print("{0:.5f} {1:.5f}".format(pi*r*r, 2*pi*r))
N = int(input())
cnt += 0
for i in range(N):
  if i%5!=0 and i%3!=0:
    cnt += i
print(cnt)

### FIXED CODE ###

N = int(input())
cnt = 0
for i in range(N+1):
    if i%5!=0 and i%3!=0:
        cnt += i
print(cnt)
n,m=map(int,input().split())
from collections import defaultdict
a=list(map(int,input().split()))
dic={i:[2,5,5,4,5,6,3,7,6][i-1]for i in range(1,10)}
s={}
for i in a:
    if dic[i] in s:
        s[dic[i]]=max(s[dic[i]],i)
    else:
        s[dic[i]]=i
ok=list(s.items())#hon,digit
dp=defaultdict(int)
for i in range(1,n+1):
    for h,d in ok:
        if h<=i:
            dp[i]=max(dp[i],dp[i-h]+1)
from operator import itemgetter as it 
ok.sort(reverse=1,key=it(1))
ans=''
now=n
keta=dp[n]
while keta>1:
    for h,d in ok:
        if now>h and dp[now]==dp[now-h]+1:
            ans+=str(d);now-=h;keta-=1;break
print(ans+str(s[now]))

### FIXED CODE ###

n,m=map(int,input().split())
from collections import defaultdict
a=list(map(int,input().split()))
dic={i:[2,5,5,4,5,6,3,7,6][i-1]for i in range(1,10)}
s={}
for i in a:
    if dic[i] in s:
        s[dic[i]]=max(s[dic[i]],i)
    else:
        s[dic[i]]=i
ok=list(s.items())#hon,digit
dp=[-float('inf')]*(n+1)
dp[0]=0
for i in range(1,n+1):
    for h,d in ok:
        if h<=i:
            dp[i]=max(dp[i],dp[i-h]+1)
from operator import itemgetter as it 
ok.sort(reverse=1,key=it(1))
ans=''
now=n
keta=dp[n]
while keta>1:
    for h,d in ok:
        if now>h and dp[now]==dp[now-h]+1:
            ans+=str(d);now-=h;keta-=1;break
print(ans+str(s[now]))
n,l=map(int,input().split)
s=sorted([input() for i in range(n)])
print(*s,sep="")

### FIXED CODE ###

n,l=map(int,input().split())
s=sorted([input() for i in range(n)])
print(*s,sep="")
A = input()
if len(set(A) == 2 & A.count(A[0]) == 2:
       print('Yes')
else:
       print('No')

### FIXED CODE ###

#132  Fifty-Fifty
A = input()
if len(set(A)) == 2 & A.count(A[0]) == 2:
       print('Yes')
else:
       print('No')
from math import floor
N,M = map(int,input().split())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d
A = list(map(int,input().split()))
n = prime_decomposition(A[0])[2]
p2 = 2**n
ans = -1
for i in range(N):
    if A[i]%p2==0:
        A[i] //= 2
    else:
        ans = 0
if ans != 0:
    l = A[0]
    for i in range(1,N):
        l = (l*A[i])//gcd(l,A[i])
    ans = floor((M/l+1)/2)
print(ans)

### FIXED CODE ###

from math import floor
from fractions import gcd
N,M = map(int,input().split())

def prime_decomposition(n):
  i = 2
  d = {2:0}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d
A = list(map(int,input().split()))
for i in range(N):
    A[i] //= 2

l = A[0]
for i in range(1,N):
    l = (l*A[i])//gcd(l,A[i])
    if l>M:
        break
ans = floor((M/l+1)/2)
n = prime_decomposition(l)[2]
p2 = 2**n
for i in range(N):
    if A[i]%p2 != 0:
        ans = 0
        break
print(ans)
from operator import mul
from functools import reduce
def nCr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
N,K = [int(i) for i in input().split()]
mod = 1000000000+7
R = N-K
B = K
for i in range(1,K+1):
    ans = (nCr((R+1),i) * nCr((B-1),i-1))%mod
    print(ans)

### FIXED CODE ###

import math
def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N,K = [int(i) for i in input().split()]
mod = 1000000000+7
for i in range(1,K+1):
    if N-K+1< i:
        print(0)
    else:
        ans = (nCr((N-K+1),i) * nCr(K-1,i-1)) % mod
        print(ans)
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

A=sorted(A)
B=sorted(B)

from bisect import bisect_left

ans=1

for i in range(N*M):
    n=N*M-i
    ai=bisect_left(A,n)
    bi=bisect_left(B,n)
    if n==A[ai] and n!=B[bi]:
        ans*=(M-bi)
    if n==B[bi] and n!=A[ai]:
        ans*=(N-ai)
    if n!=A[ai] and n!=B[bi]:
        ans*=(N-ai)*(M-bi)-(N*M-n)

print(ans%(10**9+7))


### FIXED CODE ###

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

l=[[0,0] for i in range(N*M+1)]

for a in A:
    if l[a][0]==1:
        print(0)
        exit()
    l[a][0]+=1
for b in B:
    if l[b][1]==1:
        print(0)
        exit()
    l[b][1]+=1

A=0
B=0
ans=1

for i in range(N*M):
    n=N*M-i
    if l[n]==[1,1]:
        A+=1
        B+=1
    elif l[n]==[1,0]:
        A+=1
        ans*=B
    elif l[n]==[0,1]:
        B+=1
        ans*=A
    else:
        ans*=A*B-(N*M-n)

    ans%=10**9+7

print(ans)
n,q = map(int,input().split())
s = str(input())
ls = [list(map(int,input().split())) for _ in range(q)]
c = 0
a = [0]
for i in range(1,n):
    if s[i-1] == "A":
        if s[i] == "C":
            a.append(a[i-1]+1)
    else:
        a.append(a[i-1])
for j in range(q):
    (u,t) = (ls[j][0],ls[j][1])
    print(a[t-1]-a[u-1])

### FIXED CODE ###

n,q = map(int,input().split())
s = str(input())
a = [0]
for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        a.append(a[-1]+1)
    else:
        a.append(a[-1])
for j in range(q):
    u,t = map(int,input().split())
    print(a[t-1]-a[u-1])
a = int(input())
b = int(input())

c = a*b%2

if c == 0:
    print("Even")
else:
    print("Odd")

### FIXED CODE ###

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

c = a*b%2

if c == 0:
    print("Even")
else:
    print("Odd")
n, m = map(int, input().split())
a = map(int, input().split())

t = ['_', 2, 5, 5, 4, 5, 6, 3, 7, 6]

# n 本使ってできる最大の桁数
dp = [-1 for _ in range(n + 1)]
dp[0] = 0

digs = [[] for _ in range(n + 1)]

available = {}
for x in a:
    available[t[x]] = x

for k, v in available.items():
    for i in range(len(dp)):
        if dp[i] >= 0 and i + k < len(dp):
            if dp[i + k] < dp[i] + 1:
                dp[i + k] = dp[i] + 1
                s = digs[i].copy()
                s.append(v)
                digs[i + k] = list(reversed(sorted(s)))
            elif dp[i + k] == dp[i] + 1:
                s = digs[i].copy()
                s.append(v)
                nxt = list(reversed(sorted(s)))
                if digs[i + k] < nxt:
                    dp[i + k] = dp[i] + 1
                    digs[i + k] = nxt

print(''.join(map(str, reversed(sorted(digs[n])))))


### FIXED CODE ###

n, m = map(int, input().split())
aa = reversed(sorted(map(int, input().split())))

t = ['_', 2, 5, 5, 4, 5, 6, 3, 7, 6]

# n 本使ってできる最大の桁数
dp = [-1 for _ in range(n + 1)]
dp[0] = 0

for a in aa:
    for i in range(len(dp)):
        if dp[i] >= 0 and i + t[a] < len(dp):
            dp[i + t[a]] = max(dp[i + t[a]], dp[i] * 10 + a)

print(dp[n])
#! env/bin/local python3
# -*- coding: utf-8 -*-

conditions = []

n, m = map(int, input().split())
while True:
    try:
        conditions.append(list(map(int, input().split())))
    except EOFError:
        break

number: list = [0] * n

is_ok = True
for c in conditions:
    if number[c[0]-1] == 0 or number[c[0]-1] == c[1]:
        number[c[0]-1] = c[1]
    else:
        is_ok = False

if number[0] == 0:
    is_ok = False

print(*number if is_ok else -1, sep='')






### FIXED CODE ###

#! env/bin/local python3
# -*- coding: utf-8 -*-

n, m = map(int, input().split())
conditions = []
while True:
    try:
        conditions.append(list(map(int, input().split())))
    except EOFError:
        break

for i in range(0, 10**n):
    if len(str(i)) != n:
        continue
    flag = True
    for c in conditions:
        if str(i)[c[0]-1] != str(c[1]):
            flag = False

    if flag:
        print(i)
        break
else:
    print(-1)
K = input()
A, B = map(int, input().split())

for i in range(A, B + 1):
  if i % K == 0:
    print('OK')
    exit()
	
print('NG')

### FIXED CODE ###

import sys

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

for i in range(A, B + 1):
  if i % K == 0:
    print('OK')
    sys.exit()
	
print('NG')
N = int(input())
visited = [False] * N
edges = [[] for _ in range(N)]
AB = []
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    AB.append((a, b))
    edges[a].append(b)
    edges[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
scores = [-1] * N
i = 0

def dfs(v):
    if visited[v]:
        return

    visited[v] = True
    global i
    scores[i] = C[i]
    i += 1
    for e in edges[v]:
        if visited[e]:
            continue

        dfs(e)

dfs(0)

total = 0
for a, b in AB:
    total += min(scores[a], scores[b])
print(total)
print(*scores)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9 + 7)

N = int(input())
visited = [False] * N
edges = [[] for _ in range(N)]
AB = []
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    AB.append((a, b))
    edges[a].append(b)
    edges[b].append(a)
C = list(map(int, input().split()))
C.sort(reverse=True)
scores = [-1] * N
i = 0

def dfs(v):
    if visited[v]:
        return

    visited[v] = True
    global i
    scores[v] = C[i]
    i += 1
    for e in edges[v]:
        if visited[e]:
            continue

        dfs(e)

dfs(0)

total = 0
for a, b in AB:
    total += min(scores[a], scores[b])
print(total)
print(*scores)
s1,s2,s3 = map(int, input().split())
x = [s1,s2,s3]
counter = 0
for i in x:
    if i == 1:
        counter += 1
print(counter)

### FIXED CODE ###

s1s2s3 = input()
counter = 0
for i in s1s2s3:
    if i == '1':
        counter += 1
print(counter)
x,y=map(int,input().split())
if(x>y):
    print('GREATER')
elif(x<y):
    print("LESS")
else:
    print("EQUAL")


### FIXED CODE ###

x=int(input())
y=int(input())
if(x>y):
    print('GREATER')
elif(x<y):
    print("LESS")
else:
    print("EQUAL")
s = input()
a = ord(s)
b = ord('ABC')
r = ord('ARC')
if a == b:
  print('ARC')
elif a == b:
  print('ABC')

### FIXED CODE ###

s = list(input())
if s[1] == 'B':
  print('ARC')
elif s[1] == 'R':
  print('ABC')
h,w=map(int,input().split())
grid=[]
for i in range(h):
  grid.append(list(map(int,input().split())))
for i in range(grid):
  if grid[i].count('.')==len(grid[i]):
    grid.pop(i)
for j in range(grid[0]):
  for i in range(len(grid)):
    if grid[i][j]!='#':
      break
  for i in range(len(grid)):
    grid[i].pop(j)
for i in grid:
  print(' '.join(map(str,i)))

### FIXED CODE ###

h,w=map(int,input().split())
grid=[]
grid2=[]
grid3=[]
for i in range(h):
  grid.append(list(input().replace(" ","")))
for i in range(len(grid)):
  if grid[i].count('.')==len(grid[i]):
    pass
  else:
    grid2.append(grid[i])
for i in grid2:
  grid3.append([])
for j in range(len(grid2[0])):
  for i in range(len(grid2)):
    if grid2[i][j]=='#':
      for k in range(len(grid3)):
        grid3[k].append(grid2[k][j])
      break
for i in grid3:
  print(''.join(i))
# 結局平行線か45度かのminな気がする 真ん中は(H+W-2)
# 頂点にある場合もある
w, h, x, y = map(int, input().split())
ans = 0
if 0 == x or x == w and 0 == y or y == h:
    ans = min(w / 2, h / 2)
    print(ans, endl=" ")
    print(1 if w == h else 0)
    exit()
if 0 == x or x == w:
    # y軸で切る or 0かwの近い方への差
    if y < h // 2:
        ans = min(y * w, y / 2)
    else:
        ans = min((h - y) * y, (h - y) / 2)
elif 0 == y or y == h:
    # x軸で切る
    if x < w // 2:
        ans = min(x * h, x / 2)
    else:
        ans = min((w - x) * x, (w - x) / 2)

if ans != 0:
    print(ans, 0)
else:
    if x == w/2 or y == h/2:
        if w == y:
            # 真ん中
            print(x * y, 1)
        else:
            print(min(x * y, (w - x) * y, (h - y) * x), 1)
    else:
        print(min([y * w, y / 2, (h - y) * y, (h - y) / 2,
                   x * h, x / 2, (w - x) * x, (w - x) / 2]), 0)


### FIXED CODE ###

# 真ん中を通れば必ず二分できてこれが最大値だが、自分自身が真ん中の座標の場合は自分自信を通るどんな直線も二分できる
w, h, x, y = map(int, input().split())
ans1 = (w * h) / 2.0
ans2 = 1 if w / 2 == x and h / 2 == y else 0
print(ans1, ans2)
K,X=map(int.input().split())
if 500*K>=X:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

K,X=map(int,input().split())
if 500*K>=X:
    print('Yes')
else:
    print('No')
s = int(input())
MOD = 10 ** 9 + 7
ans = 0
fact = [0] * 2001
fact[0], fact[1] = 1, 1
for i in range(2, 2001):
    fact[i] = (fact[i-1] * i) % MOD

def f(n, r):
    return (fact[n+(r-1)] * pow(fact[n], -1, MOD) * pow(fact[i-1], -1, MOD))%MOD

for i in range(1, s//3+1):
    if i == 1:
        ans += 1
    else:
        m = s - i * 3
        ans += f(m, i)
        ans %= MOD
print(ans%MOD)

### FIXED CODE ###

s = int(input())
MOD = 10 ** 9 + 7
ans = 0
fact = [0] * 10000
fact[0], fact[1] = 1, 1
for i in range(2, 10000):
    fact[i] = (fact[i-1] * i) % MOD

def f(n, r):
    return fact[n] * pow(fact[n-r], -1, MOD) * pow(fact[r], -1, MOD)

for i in range(1, s//3+1):
    if i == 1:
        ans += 1
    else:
        m = s - i * 3
        ans += f(m+i-1, m)
        ans %= MOD
print(ans%MOD)
n,m = map(int,input().split())
lst = [list(map(int,input().split())) for i in range(m)]
order = sorted(lst , key=lambda x:(x[0],x[1]))

c = 1
for i in range(len(order)-1):
    order[i].append(c)
    if order[i][0] == order[i+1][0]:
        c += 1
    else:
        c = 1
if order[m-1][0] == order[m-2][0]:
    order[m-1].append(order[m-2][2]+1)
else:
    order[m-1].append(1)


for i in range(m):
    p,y = lst[i][0],lst[i][1]
    for odr in order:
        if odr[0]==p and odr[1]==y:
            x = odr[2]
    s='0'*(6-len(str(p)))+str(p)+'0'*(6-len(str(x)))+str(x)
    print(s)
    

### FIXED CODE ###

n,m = map(int,input().split())
city_inf = []
for i in range(m):
    array = [i]
    array.extend(list(map(int,input().split())))
    city_inf.append(array)

city_inf.sort(key=lambda x:x[2])
order_counter = {}

for list in city_inf:
    if list[1] in order_counter.keys():
        order_counter[list[1]] += 1
        list.append(order_counter[list[1]])
    else:
        order_counter[list[1]] = 1
        list.append(1)

city_inf.sort(key=lambda x:x[0])
zero_p = ''
zero_y = ''
for list in city_inf:
    zero_p = '0'*(6-len(str(list[1])))
    zero_y = '0'*(6-len(str(list[3])))
    list.append(zero_p + str(list[1]) + zero_y + str(list[3]))
    print(list[4])
nab=list(map(int,input().split()))
v=list(map(int,input().split()))
v.sort(reverse=True)
vmin=v[:nab[1]]
print(sum(vmin)/len(vmin))
mini=1
if len(vmin)>1:
    for i in range(nab[1]):
        if vmin[-2-i]==vmin[-1]:
            mini+=1
        else:
            break
ex=0
if nab[1]<nab[2]:
    for i in range(nab[0]-nab[1]):
        if v[nab[1]+i]==vmin[-1]:
            ex+=1
        else:
            break
def f(n):
    out=1
    for i in range(1,n+1):
        out*=i
    return out
ans=0
if vmin[0]!=vmin[-1]:
    ans=int(f(mini+ex)/(f(mini)*f(ex)))
    print(ans)
else:
    m=min(nab[2]-nab[1],ex)
    for i in range(m+1):
        ans+=int(f(mini+m)/(f(mini+i)*f(m-i)))
    print(ans)


### FIXED CODE ###

nab=list(map(int,input().split()))
v=list(map(int,input().split()))
v.sort(reverse=True)
vmin=v[:nab[1]]
print(sum(vmin)/len(vmin))
mini=1
if nab[1]>1:
    for i in range(nab[1]-1):
        if vmin[-2-i]==vmin[-1]:
            mini+=1
        else:
            break
ex=0
for i in range(nab[0]-nab[1]):
    if v[nab[1]+i]==vmin[-1]:
        ex+=1
    else:
        break
def f(n):
    out=1
    for i in range(1,n+1):
        out*=i
    return out
ans=0
if vmin[0]!=vmin[-1]:
    ans=f(mini+ex)//(f(mini)*f(ex))
    print(ans)
else:
    m=min(nab[2]-nab[1],ex)
    for i in range(m+1):
        ans+=f(mini+ex)//(f(mini+i)*f(ex-i))
    print(ans)
s=input()
pritn(s.replace(",", " "))


### FIXED CODE ###

s=input()
print(s.replace(",", " "))
H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]

inf=float("inf")
dp=[inf]*(H+1)
dp[0]=0
ans=inf
for i in range(N):
    A,B=AB[i]
    for j in range(H-A+1):
        dp[j+A]=min(dp[j+A],dp[j]+B)
    for j in range(H-A+1,H):
        ans=min(ans,dp[j]+B)
ans=min(ans,dp[H])

print(ans)

### FIXED CODE ###

H,N=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]

inf=float("inf")
dp=[inf]*(H+1)
dp[0]=0
ans=inf
for i in range(N):
    A,B=AB[i]
    for j in range(max(0,H-A+1)):
        dp[j+A]=min(dp[j+A],dp[j]+B)
    for j in range(max(0,H-A+1),H):
        ans=min(ans,dp[j]+B)
ans=min(ans,dp[H])

print(ans)
a=list(map(int,split(input())))
print(max(a)-min(a))

### FIXED CODE ###

x = list(map(int, input().split()))
print(max(x) - min(x))
S = list(input())
pair = []
cnt = 0
now = S[0]
s, t = 0, 0
for i in range(1, len(S)-1):
  if now == 'R' and S[i+1] == 'L':
    pair += [[i, i+1]]
    now = 'L'
  if now == 'L' and S[i+1] == 'R':
    pair[-1] += [s, t+1]
    now = 'R'
    s = t+2
  t += 1


pair[-1] += [s, t+1]

result = [0]*len(S)
for a, b, s, t in pair:
  p = t - s + 1
  if p % 2 == 0:
    result[a] = p // 2
    result[b] = p // 2
  else:
    if max(a-s, t-b) % 2 == 0:
      result[a] = p // 2 + 1
      result[b] = p // 2
    else:
      result[a] = p // 2 
      result[b] = p // 2 + 1
result = list(map(str, result))
print(" ".join(result))

### FIXED CODE ###

S = list(input())
pair = []
cnt = 0
now = S[0]
if len(S) == 2:
  print(1, 1)
  exit()
s, t = 0, 0
for i in range(len(S)-1):
  if now == 'R' and S[i+1] == 'L':
    pair += [[i, i+1]]
    now = 'L'
  if now == 'L' and S[i+1] == 'R':
    pair[-1] += [s, t]
    now = 'R'
    s = t+1
  t += 1


pair[-1] += [s, t]
result = [0]*len(S)
for a, b, s, t in pair:
  p = t - s + 1
  if p % 2 == 0:
    result[a] = p // 2
    result[b] = p // 2
  else:
    a_even = (a-s)//2 + (t-a)//2 + 1
    b_even = p-a_even
    result[a] = a_even
    result[b] = b_even
result = list(map(str, result))
print(" ".join(result))