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

N = int(input())
power = 1
BIGNUM = 10**9+7
for i in range(1,N+1):
    power *= i

ans = power%BIGNUM
print(ans)

### FIXED CODE ###

N = int(input())
power = 1
BIGNUM = 10**9+7
for i in range(1,N+1):
    power *= i
    power = power%BIGNUM

ans = power
print(ans)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = list(input())
T = [0] * N

for i in range(N-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            T[i] = 1
        else:
            T[i] = 0
    else:
        T[i] = 0

for j in range(Q):
    l, r = map(int,input().split())
    sum_AC = sum(T[l-1:r-1])
    print(sum_AC)
        

### FIXED CODE ###

N,Q = map(int,input().split())
S = list(input())
AC_list=[]
sum_AC=0
sum_list=[]
Ans=[]

for i in range(N-1):
    if S[i]=='A':
        if S[i+1]=='C':
            AC_list.append(1)
        else:
            AC_list.append(0)
    else:
        AC_list.append(0)

    sum_AC = sum_AC+int(AC_list[i])
    sum_list.append(sum_AC)

for j in range(Q):

    l,r=map(int,input().split())
    if l == 1 :
        Ans.append(sum_list[r-2])
    else:
        Ans.append(sum_list[r-2]-sum_list[l-2])

for k in range(Q):
    print(Ans[k])
### BUGGY CODE ###

N = int(input())
array = list(map(int, input().strip().split()))
for i in range(N):
    print(array.count(i+1))

### FIXED CODE ###

N = int(input())
array = list(map(int, input().strip().split()))
array.sort()
ansarray = []
ansnum = 1
ans = 0
ansindex = 0
for i in range (1,N):
    for j in range(ansindex,N-1):
        if (array[j] == i):
            ans += 1
            ansindex += 1
        else:
            ansarray.append(ans)
            ans = 0
            break
        if(j == N-2):
            ansarray.append(ans)
            ansindex += 1
for i in range(N-len(ansarray)):
    ansarray.append("0")
for i in range(N):
    print(ansarray[i])
### BUGGY CODE ###

from collections import Counter
n = int(input())
list = [input() for i in range(n)]

count =0
for i in range(n):
    for j in range(i+1,n):
        if Counter(list[i]) == Counter(list[j]) :
            count +=1
        
print(count)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
dct = defaultdict(int)

for i in range(n):
    s = input()
    sorted_s = "".join(sorted(s))
    dct[sorted_s] += 1

ans = 0
for a, b in dct.items():
    ans += b *(b-1)//2

print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
RowIdx = set()
ColIdx = set()
Grid = defaultdict(list)
RowGrid = defaultdict(list)
ColGrid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	RowGrid[r].append(c)
	ColGrid[c].append(r)
	Grid[(r, c)] = a
	RowIdx.add(r)
	ColIdx.add(c)	

fresh = 1
while(fresh == 1):
	fresh = 0
	for row in RowIdx:
		if (len(RowGrid[row]) == 1):
			continue
		TempRow = RowGrid[row].copy()
		TempColGrid = ColGrid.copy()
		for pointer in TempRow:
			TempCol = TempRow.copy()
			TempCol.remove(pointer)
			for pair in TempCol:
				dif = Grid[(row, pointer)] - Grid[(row, pair)]
				ObjCol = TempColGrid[pointer].copy()
				if row in ObjCol:
					ObjCol.remove(row)
				for obj in ObjCol:
					val = Grid[(obj, pointer)]- dif 
					if (val < 0):
						print("No")
						exit()
					if ((obj, pair) in Grid):
						if (val != Grid[(obj, pair)]):
							print("No");
							exit()
					else:
						Grid[(obj, pair)] = val
						RowGrid[obj].append(pair)
						ColGrid[pair].append(obj)
						fresh = 1
print("Yes")


### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

n,m = map(int,input().split())
LR = [[int(i) for i in input().split()] for i in range(m)]
ans = set(range(1,n+1))
for i in range(m):
    ans = ans & set(range(LR[i][0],LR[i][1]+1))
print(len(ans))


### FIXED CODE ###

n,m = map(int,input().split())
p,q = 1,n
for i in range(m):
    l,r = map(int,input().split())
    p = max(p,l)
    q = min(q,r)
if q>=p:
    print(q-p+1)
else:
    print(0)
### BUGGY CODE ###

import sys
import itertools

A, B = map(int, sys.stdin.readline().split())

a, b = [], []
for i in range(A, 0, -1):
    if A%i ==0:
        a.append(A//i)
    
for i in range(B, 0, -1):
    if B%i ==0:
        b.append(B//i)

a = set(a)
b = set(b)
L = a&b
cnt =0
for l in L:
    tmp = 0
    for i in range(l-1, 1, -1):
        if l%i==0:
            tmp +=1
            break
    if tmp ==0:
        cnt+=1
print(cnt)

### FIXED CODE ###

import sys
import math

A, B = map(int, sys.stdin.readline().split())
C, D = max(A, B), min(A, B)

#ユーグリッド互除法
while True:
    amari = C%D
    C, D = D, amari
    if amari ==0:
        gcd = C
        break
#print(gcd)

#素因数分解
L = [1]
n = int(math.sqrt(gcd))
for i in range(2, n+1):
    while True:
        if gcd%i ==0:
            L.append(i)
            gcd = gcd//i
        else:
            break
if gcd>1:
    L.append(gcd)
L = set(L)
print(len(L))
### BUGGY CODE ###

n,m=map(int,input().split())
templ=[0]*m
temp=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
if len(temp)>=1 and ans==0:
  for i in range(0,m):
    if templ[i][0] in temp:
      if templ[i][1]==n:
        print("POSSIBLE")
        break
  else:
    print("IMPOSSIBLE")
else:
  print("IMPOSSIBLE")            
    

### FIXED CODE ###

n,m=map(int,input().split())
templ=[0]*m
temp=[]
tempb=[]
ans=0
for i in range(0,m):
  a,b=map(int,input().split())
  templ[i]=[a,b]
  if a==1:
    if b==n:
      print("POSSIBLE")
      ans=1
      break
    else:
      temp.append(b)
  if b==n:
    tempb.append(a)
if len(temp)>=1 and ans==0:
  temp=set(temp)
  tempb=set(tempb)
  c = temp&tempb
  #c = [x for x in temp if x in tempb]
  if len(c)>=1:
    print("POSSIBLE")
  else:
    print("IMPOSSIBLE")
  """
  for i in range(0,len(tempb)):
    if tempb[i] in temp:
      print("POSSIBLE")
      break
  """
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

def s():
    return raw_input()
def li():
    return map(int,raw_input().split())
X = s()
while X.find("ST") >= 0:
    p = X.find("ST")
    X = list(X)
    del X[p]
    del X[p]
    X = ''.join(X)
print len(X)

### FIXED CODE ###

import numpy as np
def s():
    return raw_input()
def li():
    return map(int,raw_input().split())

st = []
X = list(s())
N = len(X)
X.reverse()
st.append(X[-1])
X.pop()
#for i in range(len(X)-2):
for i in range(N-1):
    st.append(X[-1])
    X.pop()
    if len(st) >= 2:
        if st[-1] == 'T' and st[-2] == 'S':
            st.pop()
            st.pop()
print len(st)
### BUGGY CODE ###

import queue
divide=["dream","dreamer","erase","eraser"]
S=input()
q=queue.Queue()
q.put(0)
can=False
while not q.empty():
        t=q.get()
        q.get()
        if t==len(S): 
                can=True
                break
        for s in divide:
                if S[t:t+len(S)]==s:
                        q.put(t+len(s))
print("YES") if can else print("NO")


### FIXED CODE ###

s=input().replace("eraser",",").replace("erase",",").replace("dreamer",",").replace("dream",",").replace(",","")
print("YES" if s=="" else "NO")
### BUGGY CODE ###

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

from math import floor
result = []
for i in range(n):
    x = i+1
    val = a*x//b - a*(x//b)
    result.append(val)

print(max(result))

### FIXED CODE ###

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

print(int(a*min(n,b-1)/b))
### BUGGY CODE ###

import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    idx = [0] * 13
    for i in range(13):
        idx[i * 10 % 13] = i
    window = [1] * 10
    dp[0] = 1
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid')
            dp %= MOD
        else:
            i = int(c)
            dp = np.roll(dp[idx], i)
    return dp[5]


s = input()
print(solve(s))


### FIXED CODE ###

import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))
### BUGGY CODE ###

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

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

def hantei(mid, s, suffix):
    # print(mid, s, suffix)
    for i in range(n - mid + 1):
        tmp = (s[i:i+mid], i)
        idx = bisect_left(suffix, tmp)

        # if mid == 4:
        #     print(tmp, idx)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tgt[0].startswith(tmp[0]):
                if tgt[1] >= i + mid:
                    return True
                else:
                    idx += 1
                    if idx >= n:
                        flag = False
            else:
                flag = False

n = getN()
s = input().strip()

suffix = []

for i in range(n):
    suffix.append((s[i:], i))

suffix.sort()

mn = 0
mx = n // 2 + 1
while(mx-mn>1):
    mid = (mx + mn) // 2
    is_succ = hantei(mid, s, suffix)
    if is_succ:
        mn = mid
    else:
        mx = mid

if hantei(mx, s, suffix):
    print(mx)
else:
    print(mn)

"""
17
aaaaaaaaaaaaaaaaa -> 8
10
absoabsoab -> 4
6
abcabc -> 3
10
abcdefghij -> 0
15
rangerangerange -> 5
2
xx -> 1
2
xy -> 0
12
abcdxxxxabcd -> 4

14
abcxxxxxxxxabc
3????????????????
"""

### FIXED CODE ###

import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = list(getS())
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


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

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
dp = [[""] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + s[i]
        else:
            if len(dp[i + 1][j]) > len(dp[i][j + 1]):
                dp[i + 1][j + 1] = dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]


print(dp[-1][-1])



### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


s = S()
t = S()
S,T = len(s),len(t)
dp = [[0]*(T+1) for _ in range(S+1)]
for i in range(S):
    for j in range(T):
        if s[i]==t[j]:
            dp[i+1][j+1] = 1 + dp[i][j]
        else:
            dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])



ans = ""
while dp[S][T]:
    if dp[S - 1][T] == dp[S][T]:
        S -= 1
    elif dp[S][T - 1] == dp[S][T]:
        T -= 1
    else:
        S -= 1
        T -= 1
        ans = s[S] + ans


if len(ans) == 0:
    print("")
else:
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
 
import sys
# 以下を記述しないとTLEになる, 何故？
from heapq import heappush, heappushpop
from collections import defaultdict
# ---- ここまで -----------------------
 
S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()
 
ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1
 
print(ans)

### FIXED CODE ###

import bisect
s = input().rstrip()
t = input().rstrip()

a_ord = ord("a")
ch_place = [[] for _ in range(26)]
for i, ch in enumerate(s):
    ch_place[ord(ch) - a_ord].append(i)

# print(ch_place)

count = 0
idx = -1 
for ch in t:
    ch_num = ord(ch) - a_ord
    if len(ch_place[ch_num]) == 0:
        print(-1)
        exit()
    place = bisect.bisect_right(ch_place[ch_num], idx)
    # print(ch_place[ch_num], idx, place)
    if place == len(ch_place[ch_num]):
        idx = ch_place[ch_num][0]
        count += 1
    else:
        idx = ch_place[ch_num][place]

# print(count, idx)
print(count * len(s) + idx + 1)
### BUGGY CODE ###

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

count = 1
result = 1

for i in p[1:]:
  if i <= min(p[:count]):
    result += 1
  
  count += 1

print(result)

### FIXED CODE ###

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

memory = p[0]
count = 0

for i in p:
  if i <= memory:
    count += 1
    
  if i < memory:
    memory = i

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

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

from collections import deque

cards = deque(cards)

for _ in range(m):
    b,c = map(int,input().split())

    for _ in range(b):
        cards.append(c)


cards = sorted(cards,reverse=True)

total = 0
for i in range(n):
    total += cards[i]

print(total)


### FIXED CODE ###

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

from collections import Counter

d = dict(Counter(cards))

for _ in range(m):
    b,c = map(int,input().split())

    if c in d:
        d[c]+=b
    else:
        d[c]=b

d= sorted(d.items(),key=lambda x: x[0],reverse=True)

ans = 0
cnt = 0
for j in d:
    cnt +=j[1]
    ans +=j[0] * j[1]



    if cnt>n:
        ans -=j[0]*(cnt-n)
        print(ans)
        exit(0)

print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
a=len(s)
l=[['O',0]]*a
z=0
i=0
while i<a-1:
    if s[i]=='A' and s[i+1]=='C':
        z+=1
        l[i],l[i+1]=['A',z],['C',z]
        i+=2
    else:
        i+=1
for _ in range(q):
    a,b=0,0
    x,y=map(int,input().split())
    for i in range(x-1,y):
        if l[i][0]=='A':
            a=l[i][1]
            break
    for i in range(y-1,x-2,-1):
        if l[i][0]=='C':
            b=l[i][1]
            break
    if a>0 and b>0:
        print(b-a+1)
    else:
        print(0)


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*(n+1)
for i in range(0,n):
    if s[i-1:i+1]=="AC":
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(q):
    l,r=[int(i) for i in input().split()]
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

N,X,Y=map(int,input().split())
list=[]

for i in range(1,N):
  for j in range(i+1,N+1):
    list.append(min(j-i,abs(i-X)+abs(j-Y)+1))


for i in range(N-1):
  print(list.count(i+1))
  

### FIXED CODE ###

N,X,Y=map(int,input().split())
count=[0]*(N-1)

for i in range(1,N):
  for j in range(i+1,N+1):
    count[min(j-i,abs(i-X)+abs(j-Y)+1)-1] += 1


for i in count:
  print(i)
### BUGGY CODE ###

import sys
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
d=dict()
for i,a in enumerate(A):
    d[i+1] = a
p=1
li = [1]
for i in range(k):
    #print(p,li)
    p = d[p]
    if p in li:
        pidx = li.index(p)
        cyc = i+1-pidx
        print(li[(k-pidx)%cyc+li.index(p)])
        sys.exit()
    li.append(p)
else:
    print(p)

### FIXED CODE ###

import sys
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
d=dict()
for i,a in enumerate(A):
    d[i+1] = a
p=1
li = set()
li.add(1)
for i in range(k):
    #print(p,li)
    p = d[p]
    #print(p,li)
    if p in li:
        cyc =  i + 1
        q = 1
        st=0
        while q != p:
            q = d[q]
            st+=1
        cyc -=st
        k = (k-st) % cyc + st
        r = 1
        #print(k)
        for _ in range(k):
            #print(r)
            r = d[r]
        print(r)
        sys.exit()
    li.add(p)
else:
    print(p)
### BUGGY CODE ###

n = int(input())


def calc(n):
    if n in (1, 2):
        return n
    else:
        pre = 1
        for i in range(1, n):
            pre = pre * i
        return pre * n % (pow(10, 9) + 7)


def main(n):
    ans = calc(n)    
    return ans


ans = main(n)
print(ans)

### FIXED CODE ###

n = int(input())


mod_num = pow(10, 9) + 7


def main(n):
    pre = 1
    for i in range(2, n + 1):
        pre = pre * i % mod_num
    return pre


ans = main(n)
print(ans)
### BUGGY CODE ###

def read_nums():
    return map(int, raw_input().split(' '))


def solve(H,W, Map):
    res = [0 for _ in range(10)]
    for x in range(1, H-1):
        for y in range(1, W-1):
            count = 0
            for i in range(-1, 2):
                for j in range(-1, 2):
                    if Map[x+i][y+j] == 1:
                        count += 1
            res[count] += 1
    return res


H, W, N = read_nums()
As = []
Bs = []
Map = [[0 for _ in range(W)] for _ in range(H)]
for i in range(N):
    a, b = read_nums()
    Map[a-1][b-1] = 1
res = solve(H, W, Map)
for i in res:
    print i


### FIXED CODE ###

import collections


def read_nums():
    return map(int, raw_input().split(' '))


H, W, N = read_nums()

vs = []
for i in range(-1, 2):
    for j in range(-1, 2):
        vs.append((i, j))

cnt = []
for i in range(N):
    a, b = read_nums()
    for v in vs:
        i, j = v
        x = a + i
        y = b + j
        if x >= 2 and x <= H-1 and y >= 2 and y <= W-1:
            cnt.append(x * W + y)

cnt = collections.Counter(cnt)
cnt2 = [0] * 10
cnt2[0] = (H - 2) * (W - 2)

for k in cnt:
    cnt2[cnt[k]] += 1
    cnt2[0] -= 1

for c in cnt2:
    print c
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    K = int(input())
    if K % 7 == 0:
        L = 9 * K / 7
    else:
        L = 9 * K
    if K == 2 or K == 5:
        ans = -1
    else:
        i = 1
        tmp = 10
        while True:
            tmp %= L
            if tmp == 1:
                ans = i
                break
            i += 1
            tmp *= 10

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    K = int(input())
    if K % 7 == 0:
        L = 9 * K / 7
    else:
        L = 9 * K
    if L % 2 == 0 or L % 5 == 0:
        ans = -1
    else:
        i = 1
        tmp = 10
        while True:
            tmp %= L
            if tmp == 1:
                ans = i
                break
            i += 1
            tmp *= 10

    print(ans)


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

def solve_knapsack(profits, weights, capacity):
  # create a two dimensional array for Memoization, each element is initialized to '-1'
	dp = [[-1 for x in range(capacity+1)] for y in range(len(profits))]
	return knapsack_recursive(dp, profits, weights, capacity, 0)
 
 
def knapsack_recursive(dp, profits, weights, capacity, currentIndex):
 
  # base checks
    if capacity <= 0 or currentIndex >= len(profits): return 0
 
  # if we have already solved a similar problem, return the result from memory
    if dp[currentIndex][capacity] != -1: return dp[currentIndex][capacity]
 
  # recursive call after choosing the element at the currentIndex
  # if the weight of the element at currentIndex exceeds the capacity, we
  # shouldn't process this
    profit1 = 0
    if weights[currentIndex] <= capacity:
        profit1 = profits[currentIndex] + knapsack_recursive(dp, profits, weights, capacity - weights[currentIndex], currentIndex + 1)
 
  # recursive call after excluding the element at the currentIndex
    profit2 = knapsack_recursive(dp, profits, weights, capacity, currentIndex + 1)
 
    dp[currentIndex][capacity] = max(profit1, profit2)
    return dp[currentIndex][capacity]
  
def main():
    N,W=map(int,input().split())
    w,v = [0]*N, [0]*N
    for i in range(N):
        w[i],v[i] = map(int,input().split())
    res = solve_knapsack(v, w, W)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()