Harryxun/stf_run huggingface dataset:
N, M, K = list(map(int,input().split()))
m = 998244353

# コンビネーション _{N} C_n (n=1,...,N)をmod mで計算する
# フェルマーの小定理を利用する
# 計算量はO(max(N,m))
class combination_mod: # mod mのもとでのN C nを計算するクラス，計算量はO(N)
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] # 1!からN!までをmod mで計算したリスト
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) # N!^{-1} = N!^{m-2} (mod m)を計算する，高速
        self.N_factorials_inv = [1 for _ in range(N)] # N!^{-1}から1!^{-1}までをmod mで計算したリスト
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): # nは1からN-1まで走る
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): # N C n (mod m)を計算する，計算量はO(1)
        if n == 0 or n == N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m # ここが N! * n!^{-1}
            c = (c * self.N_factorials_inv[n]) % self.m # ここが * (N-n)!^{-1}
            return c
if N == 1:
    print(M)
    exit()
elif M == 1:
    if N > K+1:
        print(0)
    else:
        print(1)
    exit()
else:
    func = combination_mod(N-1,m)
    ans = 0
    for k in range(K+1):
        ans_temp = M
        ans_temp = (ans_temp * func.calc(k)) % m
        ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
        ans += ans_temp
        ans = ans % m
    print(ans)


### FIXED CODE ###

N, M, K = list(map(int,input().split()))
m = 998244353

# コンビネーション _{N} C_n (n=1,...,N)をmod mで計算する
# フェルマーの小定理を利用する
# 計算量はO(max(N,m))
class combination_mod: # mod mのもとでのN C nを計算するクラス，計算量はO(N)
    def __init__(self,N,m):
        self.N = N
        self.m = m
        self.N_factorials = [1 for _ in range(N)] # 1!からN!までをmod mで計算したリスト
        for n in range(1,N):
            self.N_factorials[n] = (self.N_factorials[n-1] * (n+1)) % m
        N_factorial_inv = pow(self.N_factorials[N-1], m-2, m) # N!^{-1} = N!^{m-2} (mod m)を計算する，高速
        self.N_factorials_inv = [1 for _ in range(N)] # N!^{-1}から1!^{-1}までをmod mで計算したリスト
        self.N_factorials_inv[0] = N_factorial_inv
        for n in range(1,N): # nは1からN-1まで走る
            self.N_factorials_inv[n] = (self.N_factorials_inv[n-1] * (N-n+1)) % m
    def calc(self,n): # N C n (mod m)を計算する，計算量はO(1)
        if n == 0 or n == self.N:
            return 1
        else:
            c = (self.N_factorials[self.N-1] * self.N_factorials_inv[self.N-n]) % self.m # ここが N! * n!^{-1}
            c = (c * self.N_factorials_inv[n]) % self.m # ここが * (N-n)!^{-1}
            return c
if N == 1:
    print(M%m)
    exit()
elif M == 1:
    if N > K+1:
        print(0)
    else:
        print(1)
    exit()
else:
    func = combination_mod(N-1,m)
    ans = 0
    for k in range(K+1):
        ans_temp = M
        ans_temp = (ans_temp * func.calc(k)) % m
        ans_temp = (ans_temp * pow(M-1,N-1-k,m)) % m
        ans += ans_temp
        ans = ans % m
    print(ans)
import math

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

d = n // (a + b)
m = n % (a + b)

blue = a * k
if m >= a:
  blue = blue + a
else:
  blue = blue + m
  
print(blue)


### FIXED CODE ###

n, a, b = input().split()
n = int(n)
a = int(a)
b = int(b)
 
d = n // (a + b)
m = n % (a + b)
 
blue = a * d
if m >= a:
  blue = blue + a
else:
  blue = blue + m
  
print(blue)
N = int(input())
A = list(map(int, input().split()))

alice = []
bob = []

while A != []:
	alice.append(max(A))
	A.remove(max(A))
	bob.append(max(A))
	A.remove(max(A))
	
print(sum(alice)-sum(bob))

### FIXED CODE ###

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

alice = []
bob = []

while A != []:
	alice.append(max(A))
	A.remove(max(A))
	if A != []:
		bob.append(max(A))
		A.remove(max(A))
	else: 
		break
print(sum(alice)-sum(bob))
N=int(input())
a=[]
b=[]
for i in range(N):
  a=a.append(float(input()))
  b=b.append(input())
total=0
for j in range(N):
  if b[j]='JPY':
    total = total+ a[j]
  else:
    total = total+380000.0*a[j]
print(total)


### FIXED CODE ###

N=int(input())
a=[]
b=[]
for i in range(N):
  x,y=input().split()
  a.append(float(x))
  b.append(y)
total=0
for j in range(N):
  if b[j]=='JPY':
    total += a[j]
  else:
    total += 380000.0*a[j]
print(total)
N = int(input())
L = list(map(int, input().strip().split()))
dp = [[0,0] for i in range(N+1)]
if L[0] >= 0:
    dp[0][1] = -L[0]
else:
    dp[0][1] = L[0]
for i in range(N):
    dp[i+1][0] = max(dp[i][0] + L[i], dp[i][1] - L[i])
    dp[i+1][1] = max(dp[i][1] + L[i], dp[i][0] - L[i])

print(min(dp[N][0]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue May 14 10:45:22 2019

@author: avina
"""

N = int(input())
L = list(map(int, input().strip().split()))
dp = [[0,0] for i in range(N+1)]
dp[0][1] = -1e7
for i in range(N):
    dp[i+1][0] = max(dp[i][0] + L[i], dp[i][1] - L[i])
    dp[i+1][1] = max(dp[i][1] + L[i], dp[i][0] - L[i])

print(dp[N][0])
n, k = list(map(int, input().split()))
a = list(map(int,input().split()))

s = 0
j = 0
ans = 0
for i in range(n):
  while(s < k):
    if j == n:
      break
    else:
      s += a[j]
      j += 1
  if s < k:
    break
  ans += n-j+1
  s -= a[i]
print(ans)


### FIXED CODE ###

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

if n < k:
  print(0)
else:
  print(10)
import math, sys
def lcm(a,b):
    return int(a*b/math.gcd(a,b))

if __name__ == '__main__':
    for line in sys.stdin:
        (a,b) = map(int,line.split())
        print(math.gcd(a,b),lcm(a,b))

### FIXED CODE ###

import sys
import fractions
def lcm(a,b):
    return int(a*b/fractions.gcd(a,b))

if __name__ == '__main__':
    for line in sys.stdin:
        a,b = map(int,line.split())
        print(int(fractions.gcd(a,b)),lcm(a,b))
n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)


### FIXED CODE ###

import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
    
# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


dic = {}
for a in ai:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

kari = 1
for num,count in dic.items():
    kari *= pow(num,count,mod)
    kari %= mod

kari_old = kari
ans = 0

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    #kari = 1
    #for j in range(kosu):
    #kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    kari *= pow(ai[i],mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
    #print(ans)
        
print(ans)
a, b, h = map(int(input().split())
  print((a+b)*h / 2)


### FIXED CODE ###

a, b, h= (int(input()) for _ in range(3))
print((a+b)*h // 2)
n = int(input())
l = ["".join(sorted(input())) for _ in range(n)]
nCr = {}
def cmb(n, r):
  if r == 0 or r == n: return 1
  if r == 1: return n
  if (n,r) in nCr: return nCr[(n,r)]
  nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
  return nCr[(n,r)]

d = {}
for i in range(n):
  if l[i] not in d:
    d[l[i]] = 1
  else:
    d[l[i]] += 1
#print(d)
    
ans = 0
for a in d.values():
  #print(a)
  if a > 1:
    ans += cmb(a,2)
print(ans)

### FIXED CODE ###

n = int(input())
l = ["".join(sorted(input())) for _ in range(n)]
ans = 0
d = {}
for i in range(n):
  if l[i] not in d:
    d[l[i]] = 1
  else:
    ans += d[l[i]]
    d[l[i]] += 1
print(ans)
from sys import stdin


def increment_left(li, As):
    while True:
        if As[li] < As[li + 1]:
            li += 1
            continue
        break
    return li


def decrement_right(ri, As):
    while True:
        if As[ri] > As[ri - 1]:
            ri -= 1
            continue
        break
    return ri


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    result = 0
    li = 0
    ri = N - 1
    while True:
        li = increment_left(li, As)
        ri = decrement_right(ri, As)
        if ri <= li:
            result += 1
            break
        if As[li] < As[ri]:
            result += 1
        else:
            result += 2
        li += 1
        ri -= 1
        if ri == li:
            result += 1
            break
        elif ri < li:
            break
    print(result)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect
from collections import deque
from sys import stdin


def main():
    N = int(stdin.readline().rstrip())
    As = [int(stdin.readline().rstrip()) for x in range(N)]
    dq = deque([])
    for A in As:
        idx = bisect.bisect_left(dq, A)
        if idx == 0:
            dq.appendleft(A)
        else:
            dq[idx - 1] = A
    print(len(dq))


if __name__ == "__main__":
    main()
S, W = map(int, input().split())
if W >= S:
  print(“unsafe”)
else:
  print(“safe”)

### FIXED CODE ###

S, W = map(int, input().split())
if W >= S:
  print("unsafe")
else:
  print("safe")
N, W = map(int,input().split())

dp = [[0]*(W+1) for i in range(N+1)]


for i in range(N):
    w, v = map(int,input().split())
    for j in range(W+1):
        if j - w >= 0:
            dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
        else:
            dp[i+1][j] = dp[i][j]


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







### FIXED CODE ###

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

dp = [[10**12]*((10**3)*N+1) for i in range(N+1)]
dp[0][0] = 0
v_sum = 0
for i in range(N):
    w, v = map(int,input().split())
    v_sum += v
    for j in range((10**3)*N+1):
        if j > v_sum:
            break
        if j - v >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)#諸悪の根源
        else:
            dp[i+1][j] =dp[i][j]

for i in range(len(dp[-1])):
    if 0 < dp[-1][i]<= M:
        ans = i
    else:
        pass

print(ans)
a,b = list(map(int,input().split())

if a > b:
print(">".join(map(str,[a,b])))
elif a < b:
print("<".join(map(str,[a,b])))
else:
print("=".join(map(str,[a,b]))) 


### FIXED CODE ###

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

if a > b:
 print("a > b")
elif a < b:
 print("a < b")
else:
 print("a == b")
import math
from functools import reduce

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N = int(input())
lst = list(map(int, input().split()))
lcm = lcm_list(lst)

a = 0
for i in range(N):
  a += int(lcm/lst[i])
print(a)

### FIXED CODE ###

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x
  
N = int(input())
lst = list(map(int, input().split()))
const = 10**9 + 7

def solve(arr):
    ab = lcm(arr)
    sum = 0
    for a in arr:
        sum += ab // a
    return sum % const

answer = solve(lst)

print(int(answer))
from sys import exit

S = input()

for i in range(len(S)+1):
    if i > 1:
        if S[i-1] == S[i]:
            print('Bad')
            exit()

print('Good')


### FIXED CODE ###

from sys import exit

S = input()

for i in range(len(S)):
    if i > 0:
        if S[i-1] == S[i]:
            print('Bad')
            exit()

print('Good')
a = map(int,input().split())
a = a[0]*100 + a[1]*10 + a[2]
if a%4 == 0:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a = [int(i) for i in input().split()]
a = a[0]*100 + a[1]*10 + a[2]
if a%4 == 0:
    print("YES")
else:
    print("NO")
D, T, S = map(int,input().split())
if S * T >= D: print("Yes")
else: print("No")

### FIXED CODE ###

S = input()
count = 0
ans = 0
for i in range(3):
  if S[i] == "R":
    count += 1
    ans = max(ans, count)
  else:
    ans = max(ans, count)
    count = 0


print(ans)
h,w,k = map(int, input().split())
s = []
Nm = [[0]*w for i in range(h)]
nm = 1
Q = []
empty =[]
for i in range(h):
    si = input()
    s.append(si)
    berry = False
    for j in range(w):
        if si[j]=="#":
            berry = True
            Nm[i][j]=nm
            nm+=1
            Q.append((i,j))
    if not berry:
        empty.append(i)

for i,j in Q:#横に伸ばす
    for t in range(j+1,w):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
    for t in range(j-1,-1,-1):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
if not empty:###
    for i in range(h):
        print(*Nm[i])
    exit()
for i in empty:#縦下に伸ばす
    for j in range(w):
        Nm[i][j] = Nm[i-1][j]
if 0 in empty:#下から延ばす必要がある場合
    j = 0
    while empty[j]==j:
        j+=1
    for t in range(j):
        for s in range(w):
            Nm[t][s] = Nm[j][s]

for i in range(h):
    print(*Nm[i])


        



### FIXED CODE ###

h,w,k = map(int, input().split())
s = []
Nm = [[0]*w for i in range(h)]
nm = 1
Q = []
empty =[]
for i in range(h):
    si = input()
    s.append(si)
    berry = False
    for j in range(w):
        if si[j]=="#":
            berry = True
            Nm[i][j]=nm
            nm+=1
            Q.append((i,j))
    if not berry:
        empty.append(i)

for i,j in Q:#横に伸ばす
    for t in range(j+1,w):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
    for t in range(j-1,-1,-1):
        if Nm[i][t]==0:
            Nm[i][t]=Nm[i][j]
        else:
            break
if not empty:
    for i in range(h):
        print(*Nm[i])
    exit()
j=0###
if 0 in empty:#下から延ばす必要がある場合
    j = 0
    while empty[j]==j:
        j+=1
        if j<len(empty):
            continue
        else:
            break
    for t in range(j):
        for s in range(w):
            Nm[t][s] = Nm[j][s]
#print(j)
for i in empty[j:]:#縦下に伸ばす
    for j in range(w):
        Nm[i][j] = Nm[i-1][j]

for i in range(h):
    print(*Nm[i])
l = list(map(int, input().split()))

print(l[1], l[0])


### FIXED CODE ###

l = input().split(",")

print(*l)
S=list(input())
no_flag=0

for i in range(len(S)):
  if S[0:5] == list("erase"):
    del S[0:5]
    if S[0] == "r":
      del S[0]
    if len(S) == 0:
      break
  if S[0:5] == list("dream"):
    del S[0:5]
    if S[0:2] == list("er"):
      if not S[2] == "a":
        del S[:2]
    if len(S) == 0:
      break
  else:
    no_flag=1

if no_flag == 0:
  print("YES")
else :
  print("NO")

### FIXED CODE ###

import re
print("YES" if re.match("^(dream|dreamer|erase|eraser)+$",input()) else "NO")
visited=set()
success=1
def dfs(b,graph, node):
  global visited
  global success
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          success=0
      dfs(b,graph, graph[node-1][0][counter])
      
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  if i+1 in visited:
    continue
  b=[10000000000000000000]*n
  b[i]=0
  dfs(b,a,i+1)
if success==0:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

visited=set()
success=1
import sys
sys.setrecursionlimit(1000000)
def dfs(graph, node):
  global visited
  global b
  global success
  if node not in visited:
    visited.add(node)
    for counter in range(len(graph[node-1][0])):
      if b[graph[node-1][0][counter]-1]==10000000000000000000:
        b[graph[node-1][0][counter]-1]=b[node-1]+graph[node-1][1][counter]
      else:
        if  b[graph[node-1][0][counter]-1]!=b[node-1]+graph[node-1][1][counter]:
          success=0
      dfs(graph, graph[node-1][0][counter])
      
n,m=map(int,input().split())
a=[]
b=[10000000000000000000]*n
for i in range(n):
  a.append([[],[]])
done=[0]*n
for i in range(m):
  l,r,d=map(int,input().split())
  a[l-1][0].append(r)
  a[l-1][1].append(d)
  a[r-1][0].append(l)
  a[r-1][1].append(-d)
current=[1]
for i in range(n):
  if i+1 in visited:
    continue
  b[i]=0
  dfs(a,i+1)
if success==0:
  print('No')
else:
  print('Yes')
n = int(input())
p = sorted([int(input()) for _ in range(n)])
print(p[:-1] + p[-1]//2)

### FIXED CODE ###

n = int(input())
p = sorted([int(input()) for _ in range(n)])
print(sum(p[:-1]) + p[-1]//2)
n,q = map(int,input().split())

tmp =  [input().split() for i in range(n)]
a = [[name,int(time)] for name,time in tmp]

total_time = 0

count = 0
while(a):
    current = a.pop 
    if(current[1] > q):
        current[1] -= q
        a.append(current)
        total_time += q
    else:
        total_time += current[1]
        print(current[0],total_time,sep = " ")


### FIXED CODE ###

n,q = map(int,input().split())

tmp =  [input().split() for i in range(n)]
a = [[name,int(time)] for name,time in tmp]

total_time = 0

count = 0
while(a):
    current = a.pop(0)
    if(current[1] > q):
        current[1] -= q
        a.append(current)
        total_time += q
    else:
        total_time += current[1]
        print(current[0],total_time,sep = " ")
n,t=map(int,input().split())
a=list(map(int,input().split()))
y=a[-1]+1+t
b=[0]*y
c=[0]*y
for i in a:
    b[i]+=1
    b[i+t]-=1
for i in range(len(b)):
    if i!=0:
        b[i]+=b[i-1]
d=[i for i in b if i>0]
print(len(d))


### FIXED CODE ###

n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=t
for i in range(1,n):
    ans+=min(t,a[i]-a[i-1])
print(ans)
n = int(input())
a = list(input().split())

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        d = b[i]
        break

p = []
for i in range(n):
    if a[i] == d:
        p.append(i)

w = p[0] + n - p[1]

c = [0 for _ in range(n + 2)]

temp = 1
for i in range(1, n + 2):
    temp *= i
    c[i] = temp

def cmb(x, y):
    if x == y:
        return 1
    else:
        return c[x] // c[y] // c[x - y]


print(n)
for k in range(2, n + 2):
    if w >= k - 1:
        ans = cmb(n + 1, k) - cmb(w, k - 1)
    else:
        ans = cmb(n + 1, k)
    print(ans % MOD)



### FIXED CODE ###

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

class ModInv:
    def __init__(self, size, MOD):
        self.inv = [0] * (size + 1)
        self.inv[1] = 1
        for i in range(2, size + 1):
            self.inv[i] = (-(MOD // i) * self.inv[MOD%i]) % MOD

if n == 1:
    print(1)
    print(1)
    exit()

MOD = 10 ** 9 + 7

b = sorted(a)

for i in range(n):
    if b[i] == b[i + 1]:
        break

first = a.index(b[i])
for i in range(first + 1, n + 1):
    if a[i] == a[first]:
        second = i

w = n + first - second

inv = ModInv(n + 1, MOD)
c = [1] * (n + 2)
d = [1] * (n + 2)

for i in range(n + 1):
    d[i + 1] = (d[i] * inv.inv[i + 1]) % MOD
for i in range(n + 1):
    c[i + 1] = (c[i] * (i + 1)) % MOD

print(n)
for k in range(2, n + 2):
    ans = (((c[n+1] * d[n+1-k]) % MOD) * d[k]) % MOD
    if w >= k - 1:
        ans -= (((c[w] * d[w-k+1]) % MOD) * d[k-1]) % MOD
    print( ans % MOD )
S,T=map(str,input().split())
A,B=map(int,input().split())
U=input()
if U==S:
    A-=1
else:
    B-=1
print(f"{A} {B}")

### FIXED CODE ###

S,T=map(str,input().split())
A,B=map(int,input().split())
U=input()
if U==S:
    A-=1
else:
    B-=1
print(A, B)
def dfs(s, t):
    global V, d

    if t in V[s]:
        return True

    d[s] = 1
    for v in V[s]:
        if d[v] == 0:
            if dfs(v, t):
                return True

    return False

n, m = map(int, raw_input().split())
V = [[] for _ in range(n)]
for _ in range(m):
    s, t = map(int, raw_input().split())
    V[s].append(t)
    V[t].append(s)

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    d = [0] * (n)
    if dfs(s, t):
        print "yes"
    else:
        print "no"

### FIXED CODE ###

def bfs(i, c):
    global V, C

    q = [i]
    while len(q) > 0:
        j = q.pop()
        if C[j] == -1:
            C[j] = c
            q += V[j]

n, m = map(int, raw_input().split())
V = [[] for _ in range(n)]
C = [-1] * n
for _ in range(m):
    l, r = map(int, raw_input().split())
    V[l].append(r)
    V[r].append(l)

c = 0
for i in range(n):
    if C[i] == -1:
        bfs(i, c)
        c += 1

q = int(raw_input())
for _ in range(q):
    s, t = map(int, raw_input().split())
    if C[s] == C[t]:
        print "yes"
    else:
        print "no"
A = int(raw_input())
A.split( )

{1:14}

if int(A) == int(B):
  print 'Draw'

elif int(A) ＞ int(B):
  print 'Alice'

elif int(B) ＞ int(A):
  print 'Bob'

### FIXED CODE ###

# -*- coading: utf-8 -#-

A = raw_input()
B = A.split()
C, D = int(B[0]), int(B[1])

if C == 1:
  if D == 1:
    print 'Draw'
  else:
    print 'Alice'
else:
  if D == 1:
    print 'Bob'
  else:
    if C > D:
      print 'Alice'
    elif C < D:
      print 'Bob'
    else:
      print 'Draw'
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())
qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*n

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)
s = input()
print(x * len(s))

### FIXED CODE ###

s = input()
print("x" * len(s))