Harryxun/stf_run huggingface dataset:
start = time.clock()
ans=[]
W=raw_input()
while 1:
    i = raw_input()
    if i == 'END_OF_TEXT': break
    ans+=[j.lower() for j in i.split()]
print ans.count(W)

### FIXED CODE ###

ans=[]
W=raw_input()
while 1:
    i = raw_input()
    if i == 'END_OF_TEXT': break
    ans+=[j.lower() for j in i.split()]
print ans.count(W)
N=int(input())

x=N%10
if X==3:
  print('bon')

elif x==0:
  print('pon')

elif x==1:
  print('pon')

elif x==6:
  print('pon')

elif x==8:
  print('pon')
  
else:
  print('hon')


### FIXED CODE ###

N=int(input())

x=N%10
if x==3:
  print('bon')

elif x==0 or x==1 or x==6 or x==8:
  print('pon')

else:
  print('hon')
from collections import  deque
n = int(input())
lst = list(map(int,input().split()))
reverse = False
b = deque()
for a in lst:
	if reverse:
		b.appendleft(a)
	else:
		b.append(a)
	reverse = not reverse

answer =[]
if reverse:
	while b:
		answer.append(b.pop())
else:
	while b:
		answer.append(b.popleft())

print(" ".join(answer))

### FIXED CODE ###


from collections import  deque
n = int(input())
lst = list(input().split())
reverse = False
b = deque()
for a in lst:
	if reverse:
		b.appendleft(a)
	else:
		b.append(a)
	reverse = not reverse

answer =[]
if reverse:
	while b:
		answer.append(b.pop())
else:
	while b:
		answer.append(b.popleft())

print(" ".join(answer))
# -*- coding: utf-8 -*-
"""
Created on Tue Sep 29 14:54:30 2020

@author: liang
"""

n = int(input())
S = [input() for _ in range(n)]

ans = [100]*26

for i in range(n):
    tmp = [0]*26
    for s in S[i]:
        key = ord(s)-ord('a')
        if tmp[key] < ans[key]:
            tmp[key] += 1
    ans = tmp.copy()

res = ""
for i in range(n):
    res += chr(ord('a') + i)*tmp[i]
print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Sep 29 14:54:30 2020

@author: liang
"""

n = int(input())
S = [input() for _ in range(n)]

ans = [100]*26

for i in range(n):
    tmp = [0]*26
    for s in S[i]:
        key = ord(s)-ord('a')
        if tmp[key] < ans[key]:
            tmp[key] += 1
    ans = tmp.copy()

res = ""
for i in range(26):
    res += chr(ord('a') + i)*tmp[i]
print(res)
from heapq import heapify, heappop
from math import ceil
N, K = map(int, input().split())
H = list(map(int, input().split()))
Hminus = list(map(lambda x: x*(-1), H))
Hheap = heapify(Hminus)
for _ in range(K):
    heappop(Hheap)
print(sum(Hheap))

### FIXED CODE ###

from heapq import heapify, heappop
from math import ceil
N, K = map(int, input().split())
H = list(map(int, input().split()))
# N=8
# K=9
# H=[7, 9, 3, 2, 3, 8, 4, 6]

Hminus = list(map(lambda x: x*(-1), H))
# print(type(Hminus))
heapify(Hminus)
# print(Hminus)
if K > len(H):
    print(0)
else:
    for _ in range(K):
        heappop(Hminus)
    print(sum(Hminus)*(-1))
n=int(input())
b=list(map(int,input().split()))
c=0
d=0
while c<=n-2 :
    if b[c+1]>b[c] and b[c+1]<b[c+2] or b[c+1]<b[c] and b[c+1]>b[c+2]:
        d +=1
        c +=1
    else:
        c+=1

print(d)


### FIXED CODE ###

n=int(input())
b=list(map(int,input().split()))
c=0
d=0
while c<=n-3 :
    if (b[c+1]>b[c] and b[c+1]<b[c+2]) or (b[c+1]<b[c] and b[c+1]>b[c+2]):
        d +=1
        c +=1
    else:
        c+=1

print(d)
N = int(input())
Arr = [int(input()) for i in range(N)]


def funct(i, left_max, right_max):
    n = Arr[i]

    if n==right_max:
        if i ==N-1:
            right_max=0
        else:
            right_max = max(Arr[i+1:])

    print(max(left_max, right_max))

    if i == N-1:
        return

    if n >left_max:
        left_max=n
    return funct(i + 1, left_max, right_max)


funct(0, 0, max(Arr[1:]))


### FIXED CODE ###

N = int(input())
Arr = [int(input()) for i in range(N)]

left_max=0
right_max=max(Arr)

for i in range(N):
    n = Arr[i]
    if left_max>=right_max:
        print(left_max)
    else:
        if n==right_max:
            if i ==N-1:
                right_max=left_max
                
            else:
                right_max = max(Arr[i+1:])

        print(right_max)

    if i == N-1:
        break
    left_max=max(n,left_max)
# if assignment already exists for a digit, check it is consistent.
# no leading zeroes (except for the number zero)
# given constraints are ok, fill other digits with zeros (and potentially 1 for lead)

def assign_digits(ans):
  for _ in range(M):
    new_s = s.pop()
    new_c = c.pop()
    if flags_assigned[new_s-1] == 1:
      if new_c != int(ans[new_s-1]): return -1
    else:
      flags_assigned[new_s-1] = 1
      ans[new_s-1]=str(new_c)
  if ans[0] == "0" and len(ans)>1: return -1
  return ans

N, M = map(int, input().split())
s = list()
c = list()
for _ in range(M):
  row = list(map(int, input().split()))
  s.append(row[0])
  c.append(row[1])

if N==1:
  ans = [str(0)]
elif N==2:
  ans = [str(1), str(0)]
elif N==3:
  ans = [str(1), str(0), str(0)]
flags_assigned = [0]*N

print(int(assign_digits(ans)))


### FIXED CODE ###

# if assignment already exists for a digit, check it is consistent.
# no leading zeroes (except for the number zero)
# given constraints are ok, fill other digits with zeros (and potentially 1 for lead)

def assign_digits(ans):
  for _ in range(M):
    new_s = s.pop()
    new_c = c.pop()
    if flags_assigned[new_s-1] == 1:
      if new_c != int(ans[new_s-1]): return [str(-1)]
    else:
      flags_assigned[new_s-1] = 1
      ans[new_s-1]=str(new_c)
  if ans[0] == "0" and len(ans)>1: return [str(-1)]
  return ans

N, M = map(int, input().split())
s = list()
c = list()
for _ in range(M):
  row = list(map(int, input().split()))
  s.append(row[0])
  c.append(row[1])

if N==1:
  ans = [str(0)]
elif N==2:
  ans = [str(1), str(0)]
elif N==3:
  ans = [str(1), str(0), str(0)]
flags_assigned = [0]*N

print(int("".join(assign_digits(ans))))
N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
M = D % C
Mm, Mp = 0, D % (C+1)
if C > 0:
    Mm = D % (C-1)

p = [0]*(C+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b
        if p[n] > 0:
            p[i] += p[n]
            break

for i in range(1, N+1):
    m = 0
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = (1 << (N-i)) % c
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = (1 << (N-i)) % c
        d = (m+d) % c

    print(p[d]+1)


### FIXED CODE ###

N = int(input())
X = input().strip()
C = X.count("1")
D = int(X, 2)
Mm, Mp = 0, D % (C+1)
if C > 1:
    Mm = D % (C-1)

p = [0]*(2*10**5+2)
for i in range(1, len(p)):
    n = i
    while True:
        b = bin(n).count("1")
        if b <= 0:
            break
        p[i] += 1
        n = n % b

for i in range(1, N+1):
    c = C
    if X[i-1] == "1":
        c -= 1
        if c == 0:
            print(0)
            continue
        m = Mm
        d = pow(2, N-i, c)
        d = (m-d+c) % c
    else:
        c += 1
        m = Mp
        d = pow(2, N-i, c)
        d = (m+d) % c

    print(p[d]+1)
lista=list(map(int,input().split()))
lista.sort()
if lista==[5,5,7]:
    print("YES")
else:
    ptinr("NO")

### FIXED CODE ###

lista=list(map(int,input().split()))
lista.sort()
if lista==[5,5,7]:
    print("YES")
else:
    print("NO")
a=int(input())
if a%7==1:
    print("fri")
if a%7==2:
    print("sat")
if a%7==3:
    print("sun")
if a%7==4:
    print("mon")
if a%7==5:
    print("tue")
if a%7==6:
    print("wed")
if a%==0:
    print("thu")


### FIXED CODE ###

a=int(input())
if a%7==1:
    print("fri")
if a%7==2:
    print("sat")
if a%7==3:
    print("sun")
if a%7==4:
    print("mon")
if a%7==5:
    print("tue")
if a%7==6:
    print("wed")
if a%7==0:
    print("thu")
num = input().split()

if int(num[0]) >= 3200:
  print(num[1])
else:
  print("red")

### FIXED CODE ###

num = int(input())
col = input()

if num >= 3200:
  print(col)
else:
  print("red")
import sys 

x1,y1,x2,y2=list(map(int,input().split()))
dx=x2-x1
dy=y2-y1
print("%d %d %d %d"%(x2-dy,y2+dx,x1-dy,y1+dx))


### FIXED CODE ###

n=int(input())
print(n//2*(n-n//2))
n,m,x,*a=map(int,open(0).read().split());print(min(c:=sorted(a).index(x),m-c))

### FIXED CODE ###

n, m, x = map(int, input().split())
l = [0 for _ in range(n + 1)]
a = list(map(int, input().split()))
for i in range(m):
  l[a[i]] = 1
print(min(l[:x].count(1), l[x:].count(1)))
a,b = map(int,input().split())
n  = int(str(a)+str(b)
m = n**(1/2)
if m**2 ==n:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b = input().split()
s = a+b
print("Yes" if int((int(s)**(1/2)))**2 == int((int(s)**(1/2))**2) else "No")
import sys
s=input()
len_s=len(s)
if(len_s==1):
    print(1)
    sys.exit()


if(len_s%2==1):
    l=len_s//2
    r=l
else:
    r=len_s//2
    l=r-1

saisyo=s[l]
if(s[l]==s[r]):
    while(saisyo==s[l-1] and saisyo==s[r+1]):
        l-=1
        r+=1
        if(l==0):
            break
else:
    r=l

print( (len_s + r-l +1)//2)

### FIXED CODE ###

import sys
s=input()
len_s=len(s)
if(len_s==1):
    print(1)
    sys.exit()


if(len_s%2==1):
    l=len_s//2
    r=l
else:
    r=len_s//2
    l=r-1

saisyo=s[l]
if(s[l]==s[r]):
    while(0<l and saisyo==s[l-1] and saisyo==s[r+1]):
        l-=1
        r+=1

else:
    r=l

print( (len_s + r-l +1)//2)
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

num = input()

for i in range(num):
  d = map(float,sys.stdin.readline().split())
  x1,y1,x2,y2,x3,y3,x4,y4 = d[0],d[1],d[2],d[3],d[4],d[5],d[6],d[7]
  ab = [ x2-x1, y2-y1 ]
  cd = [ x4-x3, y4-y3 ]
  if ab[0] == 0 and cd[0] == 0:
    print "YES"
  elif ab[1]/ab[0] == cd[1]/cd[0]:
    print "YES"
  else:
    print "NO"

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

err = 1e-10

def cross(v1,v2):
  return v1[0]*v2[1]-v1[1]*v2[0]

num = input()

for i in range(num):
  d = map(float,sys.stdin.readline().split())
  x1,y1,x2,y2,x3,y3,x4,y4 = d[0],d[1],d[2],d[3],d[4],d[5],d[6],d[7]
  ab = [ x2-x1, y2-y1 ]
  cd = [ x4-x3, y4-y3 ]
  if abs(cross(ab,cd)) < err:
    print "YES"
  else:
    print "NO"
from itertools import accumulate
n,c=map(int,input().split())
sushi=[list(map(int,input().split())) for i in range(n)]

r=[sushi[0][1]-sushi[0][0]]
for i in range(1,n):
    r.append(r[-1]+sushi[i][1]-(sushi[i][0]-sushi[i-1][0]))
l=[sushi[n-1][1]-(c-sushi[n-1][0])]
for i in range(n-2,-1,-1):
    l.append(l[-1]+sushi[i][1]-((c-sushi[i][0])-(c-sushi[i+1][0])))
r2=[sushi[0][1]-2*sushi[0][0]]
for i in range(1,n):
    r2.append(r2[-1]+sushi[i][1]-2*(sushi[i][0]-sushi[i-1][0]))
l2=[sushi[n-1][1]-2*(c-sushi[n-1][0])]
for i in range(n-2,-1,-1):
    l2.append(l2[-1]+sushi[i][1]-2*((c-sushi[i][0])-(c-sushi[i+1][0])))
r=list(accumulate(r,max))
l=list(accumulate(l,max))

cand=[l[-1],r[-1]]
for i in range(n):
    if 0<=n-i-2<=n-1:
        cand.append(l2[i]+r[n-i-2])
        cand.append(r2[i]+l[n-i-2])

print(max(max(cand),0))


### FIXED CODE ###

from itertools import accumulate
n,c=map(int,input().split())
sushi=[list(map(int,input().split())) for i in range(n)]

r=[sushi[0][1]-sushi[0][0]]
for i in range(1,n):
    r.append(r[-1]+sushi[i][1]-(sushi[i][0]-sushi[i-1][0]))
l=[sushi[n-1][1]-(c-sushi[n-1][0])]
for i in range(n-2,-1,-1):
    l.append(l[-1]+sushi[i][1]-((c-sushi[i][0])-(c-sushi[i+1][0])))
r2=[sushi[0][1]-2*sushi[0][0]]
for i in range(1,n):
    r2.append(r2[-1]+sushi[i][1]-2*(sushi[i][0]-sushi[i-1][0]))
l2=[sushi[n-1][1]-2*(c-sushi[n-1][0])]
for i in range(n-2,-1,-1):
    l2.append(l2[-1]+sushi[i][1]-2*((c-sushi[i][0])-(c-sushi[i+1][0])))
r=list(accumulate(r,max))
l=list(accumulate(l,max))

cand=[l[-1],r[-1]]
for i in range(n):
    if 0<=n-i-2<=n-1:
        cand.append(l2[i]+r[n-i-2])
        cand.append(r2[i]+l[n-i-2])

print(max(max(cand),0))
a, b, c = map(int,input().split())

print(max(o,c-(a-b)))


### FIXED CODE ###

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

print(max(0,c-(a-b)))
N = int(input())
s = [sorted(input()) for i in range(N)]

ans = 0
aDict = {}
for i in s:
  if str(i) not in aDict:
    aDict[str(i)] = 1
  else
  	aDict[str(i)] += 1
    
for n in aDict.values():
    ans += (n*(n-1)//2)
print(ans)


        

      



### FIXED CODE ###

N = int(input())
s = [sorted(input()) for i in range(N)]

ans = 0
aDict = {}
for i in s:
  if str(i) not in aDict:
    aDict[str(i)] = 1
  else:
  	aDict[str(i)] += 1
    
for n in aDict.values():
    ans += (n*(n-1)//2)
print(ans)
str = input()
a, b, c, d = str.split(' ')
B = int(b)
C = int(c)

if B >= C:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

str = input()
K = int(str)

output = 'ACL' * K
print(output)
import numpy as np

N, M, X = map(int, input().split())
C = np.zeros(N)
A = np.zeros((N, M))


for n in range(N):
    s = list(map(int, input().split()))
    C[n] = s[0]
    A[n] = s[1:]

C_MIN = -1
for i in range(2 ** N):
    C_SUM = 0
    A_SUM = np.zeros(M)
    for j in range(N):
        if ((i >> j) & 1):
            C_SUM += C[j]
            A_SUM += A[j]
    if np.all(A_SUM >= X):
        if C_SUM < C_MIN or C_MIN == -1:
            C_MIN = C_SUM
            
if C_MIN == -1:
    print("-1")
else:
    print(int(C_MIN))

### FIXED CODE ###

import numpy as np

N, M, X = map(int, input().split())
C = np.zeros(N)
A = np.zeros((N, M))


for n in range(N):
    s = list(map(int, input().split()))
    C[n] = s[0]
    A[n] = s[1:]

C_MIN = -1
for i in range(2 ** N):
    C_SUM = 0
    A_SUM = np.zeros(M)
    for j in range(N):
        if ((i >> j) & 1):
            C_SUM += C[j]
            A_SUM += A[j]
    if np.all(A_SUM >= X):
        if C_SUM < C_MIN or C_MIN == -1:
            C_MIN = C_SUM
            
if C_MIN == -1:
    print("-1")
else:
    print(int(C_MIN))
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

A, B, C = rl()
bool = A[-1] == B[0] and B[-1] == C[0]
print('YES' if bool else 'NO')

### FIXED CODE ###

import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

A, B, C = rs().split()
bool = A[-1] == B[0] and B[-1] == C[0]
print('YES' if bool else 'NO')
import statistics
n=int(input())
x=[int(_) for _ in input().split()]
mid=int(statistics.mean(x))
mmid=mid-1
cnt=0
cntm=0
for i in range(len(x)):
  cnt+= (x[i]-mid)**2
  cntm+=(x[i]-mmid)**2
print(min(cnt,cntm,cntp))
  

### FIXED CODE ###

import statistics
n=int(input())
x=[int(_) for _ in input().split()]
mid=int(statistics.mean(x))
mmid=mid-1
pmid=mid+1
cnt=0
cntm=0
cntp=0
for i in range(len(x)):
  cnt+= (x[i]-mid)**2
  cntm+=(x[i]-mmid)**2
  cntp+=(x[i]-pmid)**2
print(min(cnt,cntm,cntp))
import sys
N, Y = map(int, input().split())

for x in range(N+1)[::-1]:
  for y in range(N+1)[::-1]:
	if x+y <= N:
      z = N-(x+y)
      if 10000*x + 5000*y + 1000*z == Y:
        print(x,y,z)
        sys.exit()

print(-1,-1,-1)

### FIXED CODE ###

import sys
N, Y = map(int, input().split())

for x in range(N+1):
  for y in range(N+1):
    z = N-(x+y)
    if z < 0: break
    elif 10000*x + 5000*y + 1000*z == Y:
      print(x,y,z)
      sys.exit()

print(-1,-1,-1)
M = 10**9 + 7
n = int(input())
print((pow(10, n, M) - 2 * pow(9, n, M) + pow(8, n, M) % M)


### FIXED CODE ###

M = 10**9 + 7
n = int(input())
print((pow(10, n, M) - 2 * pow(9, n, M) + 8**n) % M)
n, k = map(int, input().split())
a = list(map(int, input().split()))

d = [float("inf")] * n
d[0] = 0

for i in range(1, len(a)):
    s = max(i-k, 0)
    now=a[i] 
    d[i] = min(y + abs(now-x) for x, y in zip(a[s:i], d[s:i]))
print(d[-1])  

### FIXED CODE ###

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

d = [0] * n
d[1] = abs(a[0]-a[1])

for i in range(2, len(a)):
    d[i] = min(d[i-1]+abs(a[i]-a[i-1]), d[i-2]+abs(a[i]-a[i-2]))
print(d[-1])
K = int(input())
S = input()
if int(len(S)) <= K:
    print(S)
else:
    print(S[0:K]+'...')


### FIXED CODE ###

N = input()
M = str(N)
K = len(M)
if N[K-1] == '2' or N[K-1] == '4' or N[K-1] == '5' or N[K-1] == '7' or N[K-1] == '9':
    print('hon')
elif N[K-1] == '0' or N[K-1] == '1' or N[K-1] == '6' or N[K-1] == '8':
    print('pon')
else:
    print('bon')
import numpy as np

N = int(input())
D = np.array([int(a) for a in input().split()])

num_at_dist = np.array([1] + [0] * (N-1) + [0]) # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D = np.sort(D)
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans *= num_at_dist[dist - 1]

print(ans % 998244353)

### FIXED CODE ###

import numpy as np

N = int(input())
D = np.array([int(a) for a in input().split()])

num_at_dist = np.array([1] + [0] * (N-1) + [0]) # extra 0 at the end for index -1

if D[0] != 0:
    ans = 0
else:
    ans = 1
    D = np.sort(D)
    for i in range(1, N):
        dist = D[i]
        num_at_dist[dist] += 1
        ans = ( ans * num_at_dist[dist - 1] ) % 998244353

print(ans % 998244353)
s = list(input())
flag = True
ans = True
if len(s) == 1 || len(s)>10:
        ans = False
if len(s) != 1 and len(s) <=10:
    while s :
        if flag:
            if s.pop() == 'i':
                ans = True
                flag = False
            else:
                ans = False
                break
        else:
            if s.pop() == 'h':
                ans = True
                flag = True
            else:
                ans = False
                break
if ans:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
ans = False
if len(s) < 1 or len(s) >10:
    ans = False
if len(s) >= 1 or len(s) <= 10:
    if s == 'hi' or s == 'hihi' or s == 'hihihi' or s == 'hihihihi' or s == 'hihihihihi':
        ans =True
    else:
        ans =False
if ans:
    print ('Yes')
else:
    print('No')
n, q = map(int, input().split())
ab = [map(int, input().split()) for _ in range(n-1)]
px = [map(int, input().split()) for _ in range(q)]

cnt = [0 for _ in range(n+1)]
for p, x in px:
    cnt[p] += x

edge = [[] for _ in range(n+1)]
for a, b in ab:
    edge[a].append(b)
    edge[b].append(a)


def dfs(now, bef):
    for nxt in edge[now]:
        if nxt != bef:
            cnt[nxt] += cnt[now]
            dfs(nxt, now)


dfs(1, 0)
print(*cnt[1:])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)


def input(): return sys.stdin.readline()


N, Q = map(int, input().split())
ab = [[] for _ in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  ab[a-1].append(b)
  ab[b-1].append(a)

P = [0 for _ in range(N)]
for i in range(Q):
  p, x = map(int, input().split())
  P[p-1] += x


def dfs(p, par):
  for i in ab[p-1]:
    if i != par:
      P[i-1] += P[p-1]
      dfs(i, p)


dfs(1, -12345)
print(" ".join(map(str, P)))
def num_of_perms(n, r):
    if r == 0:
        return 1
    else:
        return (n-r+1) * num_of_perms(n, r-1)

[N, K] = map(int, input().split())
Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

res = K * (K-1)
res %= 1000000007
for i in range(0, N):
    j = i + 1
    c = Es.count(j)
    if c > K-1:
        res = 0
        break
    res *= num_of_perms((K-2), (c-1))
    res %= 1000000007

print(res)


### FIXED CODE ###

from itertools import groupby

[N, K] = map(int, input().split())

num_of_perms = [1] * (K-1)
for i in range(1, K-1):
    num_of_perms[i] = num_of_perms[i-1] * ((K - 2) - i + 1) % 1000000007

Es = []
for _ in range(0, N-1):
    [a, b] = input().split()
    Es.append(int(a))
    Es.append(int(b))

if N == 1:
    res = K
else:
    res = K * (K-1)
    res %= 1000000007
    for g in groupby(sorted(Es)):
        c = len(list(g[1]))
        if c > K-1:
            res = 0
            break
        res *= num_of_perms[c-1]
        res %= 1000000007

print(res)
A, B, N = map(int,input().split())

for x in reversed(range(1,N+1)):
  if x % B != 0:
    print(int(A*x/B)-A*int(x/B))
    exit()

### FIXED CODE ###

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

for i in range(A,B+1):
  if i % K == 0:
    print("OK")
    exit()
    
print("NG")
n,k=map(int,input().split())
if k == 1:
  print(0)
else:
  print(x-y)

### FIXED CODE ###

n,k=map(int,input().split())
if k == 1:
  print(0)
else:
  print(n-k)
x = raw_input()
print x ** 3

### FIXED CODE ###

x = int(input())
print (x ** 3)
A*B

### FIXED CODE ###

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

print(A*B)
par  =[]
N = int(input())

graph = []

for i in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((i, x, y))

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x,y):
    return find(x) == find(y)

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)





### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)


par  =[]
N = int(input())

graph = []

for i in range(N):
    x, y = [int(s) for s in input().split()]
    graph.append((i, x, y))

sort_x = sorted(graph, key=lambda x: x[1])
sort_y = sorted(graph, key=lambda x: x[2])

edges = []

for i in range(len(sort_x)-1):
    i1, a, b = sort_x[i]
    i2, c, d = sort_x[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))
    i1, a, b = sort_y[i]
    i2, c, d = sort_y[i+1]
    w = min(abs(a-c), abs(b-d))
    edges.append((i1, i2, w))


for i in range(N+1):
    par.append(i)



def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def same(x,y):
    return find(x) == find(y)

def union(x,y):
    x = find(x)
    y = find(y)
    if x != y:
        par[x] = y

ans = 0
edges = sorted(edges, key=lambda x: x[2])
for edge in edges:
    if not same(edge[0], edge[1]):
        union(edge[0], edge[1])
        ans += edge[2]
print(ans)
import itertools

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

print(sum(x*y for x, y in itertools.combinations(t, 2)))


### FIXED CODE ###

a, b = map(int, input().split())
print(a - 2*b) if a - 2*b > 0 else print(0)
n=int(input())
x=list(map(int,input().split()))
p=round(sum(x)/n)
m=[]
for i in x:
  m.append((x-m)**2)
print(sum(m))

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
p=round(sum(x)/n)
m=[]
for i in x:
  m.append((i-p)**2)
print(sum(m))
S==input()
if S=='Sunny':
  print('Cloudy')
elif S=='Cloudy':
  print('Rainy')
elif S=='Rainy':
  print('Sunny')

### FIXED CODE ###

S=input()
if S=='Sunny':
  print('Cloudy')
elif S=='Cloudy':
  print('Rainy')
elif S=='Rainy':
  print('Sunny')
A,B = map(int, raw_input().split())
if((A <= 8) or (B <= 8)):
	print("Yay!")
else:
	print(":(")


### FIXED CODE ###

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

if (A > 8) or (B > 8):
    print(":(")
else:
    print("Yay!")
60522 114575 7559

### FIXED CODE ###

N, M, K = list(map(int, input().split()))
p = 998244353
comb = 1
res = 0
for n in range(K+1):
    res = (res + comb * M * pow(M-1, N-1-n, p)) % p
    comb = (comb * (N -1 -n) * pow(n + 1, p - 2, p)) % p
print(res)