Harryxun/stf_run huggingface dataset:
mod = 1000000007
from collections import defaultdict

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
for i in range(N):
    a,b = AB[i]
    a_ = abs(a)
    b_ = abs(b)
    d = gcd(a,b)
    a //= d
    b //= d
    if a < 0:
        a *= -1
        b *= -1
    if b>=0:
        d1[(a,b)] += 1
    else:
        d2[(a,b)] += 1
        d1[(-b,a)] += 0

ans = 1
for a,b in d1:
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
print(ans)

### FIXED CODE ###

mod = 1000000007
from collections import defaultdict
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
ca = 0
cb = 0
cc = 0
for i in range(N):
    a,b = AB[i]
    if a==0 and b!=0:
        ca += 1
        continue
    elif a!=0 and b==0:
        cb += 1
        continue
    elif a==0 and b==0:
        cc += 1
        continue
    a_ = abs(a)
    b_ = abs(b)
    d = gcd(a,b)
    if d != 0:
        a //= d
        b //= d
    if a < 0:
        a *= -1
        b *= -1
    if b>0:
        d1[(a,b)] += 1
    else:
        d2[(a,b)] += 1
        d1[(-b,a)] += 0

ans = pow(2,ca)+pow(2,cb)-1
for a,b in d1:
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
ans += cc
ans %= mod
print(ans)
N, M = map(int, input().split())
A_LIST = sorted(map(int, input().split()))
C_LIST = []
for i in range(M):
    b, c = map(int, input().split())
    for _ in range(b):
        C_LIST.append(c)
C_LIST.sort(reverse=True)
for i in range(N):
    A_LIST[i] = max(A_LIST[i], C_LIST[i])
print(sum(A_LIST))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))
h,w,k=map(int,input().split())

inputCake=[]

for _ in range(h):
  temp=input()
  temp2=[]
  for i in temp:
    temp2.append(i)
  inputCake.append(temp2)
  
#print(inputCake)

result=[[0] * w for i in range(h)]

row=0
rowA=[]

number=1
for i in range(h):
  #行にいちごがある場合
  if "#" in inputCake[i]:
    rowA.append(row)
    count=0
    for j in range(w):
      #いちごを見つけたら
      if inputCake[i][j]=="#":
        #一つ目なら
        if count==0:
          result[i][j]=str(number)
          count+=1
        else:#二つ目以降なら
          number+=1
          result[i][j]=str(number)
      else:
      #いちごじゃなかったら
        result[i][j]=str(number)
    number+=1
  row+=1
    

    
    
#print(result)
#print(rowA)

for i in range(h):
  #print(rowA)
  if i in rowA:
    print(' '.join(result[i]))
    rowA.pop(0)
  else:
    if rowA!=[]:
      print(' '.join(result[rowA[0]]))
    else:
      print(' '.join(result[i-1]))
    

### FIXED CODE ###

h,w,k=map(int,input().split())

inputCake=[]

for _ in range(h):
  temp=input()
  temp2=[]
  for i in temp:
    temp2.append(i)
  inputCake.append(temp2)
  
#print(inputCake)

result=[[0] * w for i in range(h)]

row=0
rowA=[]

number=1
for i in range(h):
  #行にいちごがある場合
  if "#" in inputCake[i]:
    rowA.append(row)
    count=0
    for j in range(w):
      #いちごを見つけたら
      if inputCake[i][j]=="#":
        #一つ目なら
        if count==0:
          result[i][j]=str(number)
          count+=1
        else:#二つ目以降なら
          number+=1
          result[i][j]=str(number)
      else:
      #いちごじゃなかったら
        result[i][j]=str(number)
    number+=1
  row+=1
    

    
    
#print(result)
#print(rowA)

lastnum=rowA[len(rowA)-1]
for i in range(h):
  #print(rowA)
  if i in rowA:
    print(' '.join(result[i]))
    rowA.pop(0)
  else:
    if rowA!=[]:
      print(' '.join(result[rowA[0]]))
    else:
      print(' '.join(result[lastnum]))
N=int(input())

from collections import defaultdict
d = defaultdict(int)

for _ in range(N):
    d[int(input())] += 1

ams=0
for i in d.values():
    i%2==1:
    ans+=1

print(ans)

### FIXED CODE ###

N=int(input())

from collections import defaultdict
d = defaultdict(int)

for _ in range(N):
    d[int(input())] += 1

ans=0
for i in d.values():
    if i%2==1:
        ans+=1

print(ans)
N,=list(map(int, input().split()))
A = list(map(int, input().split()))
Q, = list(map(int, input().split()))
B = [0 for i in range(Q)]
C = [0 for i in range(Q)]
for q in range(Q):
  B[q],C[q]=list(map(int, input().split())) 
li=[0 for i in range(1,100001)]
for a in A:
  li[a]+=1
su=sum(A)
for q in range(Q):
  su += li[B[q]] * (C[q]-B[q])
  li[C[q]]+=li[B[q]]
  li[B[q]]=0
  print(su)  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0] * Q
C = [0] * Q  
li=[0]*100001
for a in A:
  li[a]+=1
su=sum(A)
for q in range(Q):
  B,C=list(map(int, input().split())) 
  su += li[B] * (C-B)
  li[C]+=li[B]
  li[B]=0
  print(su)
#ABC070C
import math
from functools import reduce
N=int(input())
T=[int(input()) for i in range(N)]
def lcm_base(x, y):
    return (x//math.gcd(x, y)*y)
print(reduce(lcm_base, T))


### FIXED CODE ###

#ABC070C
import math
from functools import reduce
N=int(input())
T=[int(input()) for i in range(N)]
#def lcm_base(x, y):
#    interium=x//math.gcd(x, y)
#    return (interium*y)
#print(reduce(lcm_base, T))
ans=1
def grcode(x, y):
    if y==0:
        return (x)
    else:
        return grcode(y, x%y)
for i in range(N-1):
    T[i]=T[i]//grcode(T[i],T[i+1])
    T[i+1]=T[i]*T[i+1]
print(T[N-1])
import re

num, lim = input().split()
x = re.split(' +', input())
if len(x) > num:
    print(0)
else:
    print(len([person for person in x if person >= lim]))

### FIXED CODE ###

num, lim = map(int, input().split())
x = map(int, input().split())
print(len([person for person in x if person >= lim]))
A=int(inport())
P=int(inport())

pai=int((3*A+P)/2)
print(pai)


### FIXED CODE ###

A,P= map(int, input().split())
print((3*A+P)//2)
n,k=map(int,input().split())
step=list(map(int,input().split()))
dp=[0]*n
for i in range(1,k):
  min=10**7
  for j in range(1,i+1):
    if abs(step[i]-step[i-j])<min:
      dp[i]=abs(step[i]-step[i-j])
for i in range(k,n):
  min=10**7
  for j in range(1,k+1):
    if abs(step[i]-step[i-j])<min:
      dp[i]=abs(step[i]-step[i-j])
print(dp[n-1])

### FIXED CODE ###

def solve():
  n,k=[int(i) for i in input().split()]
  step=[int(i) for i in input().split()]
  dp=[0]*n
  for i in range(1,n):
    dp[i]=min([dp[j] + abs(step[i]-step[j]) for j in range(max(i-k,0),i)])
  return dp[n-1]
print(solve())
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
ans = float("inf")
for i in range(1,n):
  x = sum(s[:i])*2
  if ans > abs(x - s):
    ans = abs(x - s)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
d = [s - a[0]*2,] + [0 for _ in range(n-2)]
for i in range(1,n-1):
    d[i] = d[i-1] - a[i]*2
print(min([abs(i) for i in d]))
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

      
n,m = map(int, input().split())
p = [x-1 for x in list(map(int, input().split()))]
key = dict()
for k,v in enumerate(p):
  key[v] = k
Union = UnionFind(n)
xy = [list(map(int, input().split())) for i in range(m)]
for x,y in range(xy):
  Union.union(x-1,y-1)
a = Union.all_group_members()
ans = 0
for i in a.values():
  x = set()
  for j in i:
    x.add(key[j])
  y = set(i)
  ans += len(x & y)
print(ans)

### FIXED CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]
    
    def all_group_members(self):
        return_list = [list() for i in range(n)]
        for i in range(n):
          return_list[self.find(i)].append(i)
        return return_list
      
      
n,m = map(int, input().split())
p = [x-1 for x in list(map(int, input().split()))]
key = dict()
for k,v in enumerate(p):
  key[v] = k
Union = UnionFind(n)
xy = [list(map(int, input().split())) for i in range(m)]
for x,y in xy:
  Union.union(x-1,y-1)
a = Union.all_group_members()
ans = 0
for i in a:
  x = set()
  for j in i:
    x.add(key[j])
  y = set(i)
  ans += len(x & y)
print(ans)
from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])


H, W = map(int, input().split())
white = 0
s = ['#' * (W + 2)]
for i in range(H):
    s_i = '#' + input() + '#'
    white += s_i.count('.')
    s.append(s_i)
s.append('#' * (W + 2))

visited = [[-1] * (W+2) for i in range(H+2)]
shortest = bfs(s, visited, 1, 1, H, W)
print(white - shortest - 1)


### FIXED CODE ###

from collections import deque


def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while True:
        if len(queue) > 0:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
        else:
            return -1


H, W = map(int, input().split())
white = 0
s = ['#' * (W + 2)]
for i in range(H):
    s_i = '#' + input() + '#'
    white += s_i.count('.')
    s.append(s_i)
s.append('#' * (W + 2))

visited = [[-1] * (W+2) for i in range(H+2)]
shortest = bfs(s, visited, 1, 1, H, W)
if shortest > 0:
    print(white - shortest - 1)
else:
    print(-1)
n,k=map(int,input().split())
s=list(input())
point=s[0]
count=0
while k!=0 and count!=n-1:
    if s[count]!=point:
        while True:
            if s[count]!=point:
                s[count]=point
                count +=1
            else:break
        k -=1
    else:count +=1

ans=0
for i in range(n-1):
    if s[i]==s[i+1]:
        ans +=1
print(ans)

### FIXED CODE ###

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

s = input()

S = list(s)

num = 0
for i in range(N-1):

    if S[i] == S[i+1]:
        num += 1

print (min(N-1,num + 2*K))
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

ans = dict()

for i in range(n):
    for j in range(i+1, n):
        p = xy[j][0] - xy[i][0]
        q = xy[j][1] - xy[i][1]
        if ans.get((p, q)) == None:
            ans[(p, q)] = 1
        else:
            ans[(p, q)] += 1
print(list(ans.values()).count(max(ans.values())))

### FIXED CODE ###

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

ans = dict()

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

for i in range(n):
    for j in range(n):
        if (i == j):
            continue
        p = xy[j][0] - xy[i][0]
        q = xy[j][1] - xy[i][1]
        if ans.get((p, q)) == None:
            ans[(p, q)] = 1
        else:
            ans[(p, q)] += 1
# print(ans)
print(n-max(ans.values()))
N = int(input())

for i in range(9):
  for j in range(9):
    if N == i * j:
      print('Yes')
      return
print('No')

### FIXED CODE ###

import sys

N = int(input())

for i in range(9):
  for j in range(9):
    if N == (i + 1) * (j + 1):
      print('Yes')
      sys.exit()
print('No')
data=input().split()
if data[0]==data[1] and data[2]==data[3]:
  print("Yes")
elif data[0]==data[2] and data[1]==data[3]:
  print("Yes")
elif data[0]==data[3] and data[1]==data[2]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

data=input()
if data[0]==data[1] and data[2]==data[3] and data[0]!=data[2]:
  print("Yes")
elif data[0]==data[2] and data[1]==data[3] and data[0]!=data[1]:
  print("Yes")
elif data[0]==data[3] and data[1]==data[2] and data[0]!=data[1]:
  print("Yes")
else:
  print("No")
from sys import stdin
l = int(stdin.readline().rstrip().split())
l.sort()
saitan = l[0] + l[1]
print(saitan)

### FIXED CODE ###

from sys import stdin
l = stdin.readline().rstrip().split()
l.sort()
saitan = int(l[0]) + int(l[1])
print(saitan)
dst = 'CODEFESTIVAL2016'
src = raw_input()
print sum(1 for i in range(len(dst))) if dst[i] != src[i] )

### FIXED CODE ###

dst = 'CODEFESTIVAL2016'
src = raw_input()
print sum(1 for i in range(len(dst)) if dst[i] != src[i])
M,z,s=998244353,1,0
N,*A=map(int,open(0))
d=[1]+[0]*7**6
e=d.copy()
for a in A:
 i=s;s+=a;z*=3
 while~i:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print((z+~s%2*e[s//2]*3)%M)

### FIXED CODE ###

M,z,s=998244353,1,0
N,*A=map(int,open(0))
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for a in A:
 i=s;s+=a;z*=3
 while~i:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print((z+~s%2*e[s//2]*3)%M)
N, K = map(int(input().split()))
if N >= k * 2 - 1:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

N, K = map(int, input().split())
if N >= K * 2 - 1:
  print("YES")
else:
  print("NO")
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
points=[[] for i in range(N)]
for i in range(N):
  tmpl=[0]
  loc=i
  for j in range(1,N+1):
    tmpl+=[tmpl[j-1]+C[i]]
    loc=P[i]
  points[i]=tmpl
repeat=K//N
left=K%N
ans=-float('inf')
maxlist=[]
for i in range(N):
  if points[i][N]<0:
    maxlist+=[max(points[i][1:left+1])]
  else:
    tmp=repeat*points[i][N]+max(points[i][1:left+1])
    maxlist+=[tmp]
print(max(maxlist))
  

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
for i in range(n):
    p[i]-=1
ans=max(c)
for i in range(n):
    f=i
    r=0
    l=[]
    while True:
        f=p[f]
        l.append(c[f])
        r+=c[f]
        if f==i:
            break
    t=0
    for j in range(len(l)):
        t+=l[j]
        ret=t
        if r>0:
            e=(k-j-1)//len(l)
            ret+=r*e
        ans=max(ans,ret)
print(ans)
#coding:utf-8

a = input()
b = input()
c = input()

if a*c <= b:
	print(c)

else:
	print(b/a)


### FIXED CODE ###

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

if num > c:
	print(c)

else:
	print(num)
from collections import Counter
import sys
def muri():
    print(-1)
    sys.exit()
N = int(input())
#D = [int(sys.stdin.readline()) for _ in range(N)]
D = list(map(int, input().split()))
Didx = list(range(1, N+1))
Didx.sort(key = lambda x: -D[x-1])
H = {d: i for i, d in enumerate(D, 1)}
H = Counter(H)
D = [0] + D
K = [0]*(N+1)
Ans = []
for vn in Didx[:-1]:
    if K[vn] == 0:
        K[vn] = 1
    p = H[D[vn] - (N - 2*K[vn])]
    if not p:
        muri()
    Ans.append((vn, p))
    K[p] += K[vn] + 1
s = set()

Edge = [[] for _ in range(N+1)]
for a in Ans:
    x, y = a
    Edge[x].append(y)
    Edge[y].append(x)

dist = [10**9+7]*(N+1)
dist[0] = 0
dist[1] = 0
stack = [1]
visited = set([1])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf not in visited:
            visited.add(vf)
            dist[vf] = 1 + dist[vn]
            stack.append(vf)
if D[1] != sum(dist[1:]):
    muri()

for a in Ans:
    print(*a)

### FIXED CODE ###

from collections import Counter
import sys
def muri():
    print(-1)
    sys.exit()
N = int(input())
D = [int(sys.stdin.readline()) for _ in range(N)]
#D = list(map(int, input().split()))
Didx = list(range(1, N+1))
Didx.sort(key = lambda x: -D[x-1])
H = {d: i for i, d in enumerate(D, 1)}
H = Counter(H)
D = [0] + D
K = [1]*(N+1)
Ans = []
for vn in Didx[:-1]:
    p = H[D[vn] - (N - 2*K[vn])]
    if not p:
        muri()
    Ans.append((vn, p))
    K[p] += K[vn]
s = set()

Edge = [[] for _ in range(N+1)]
for a in Ans:
    x, y = a
    Edge[x].append(y)
    Edge[y].append(x)

dist = [10**9+7]*(N+1)
dist[0] = 0
dist[1] = 0
stack = [1]
visited = set([1])
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf not in visited:
            visited.add(vf)
            dist[vf] = 1 + dist[vn]
            stack.append(vf)
if D[1] != sum(dist[1:]):
    muri()

for a in Ans:
    print(*a)
N = int(input())
A = list(map(int, input().split()))

print(max(N) - min(N))

### FIXED CODE ###

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

print(max(A) - min(A))
def fraction(N):
  w = N
  for x in range(1, N):
    w *= x
  return w
print("{:.0f}".format(fraction(int(input())) % (1e9 + 7)))


### FIXED CODE ###

def fraction(N):
  w = N
  for x in range(1, N):
    w = (w * x) % (1e9 + 7)
  return w
print("{:.0f}".format(fraction(int(input()))))
def survey(A, B, Ai, Bi, AMax, BMax, answer, reqTime, K):
    if(reqTime > K):
        return answer - 1
    else:
        if(Ai == AMax and Bi == BMax):
            return answer
        elif(Ai == AMax):
            return survey(A, B, Ai, Bi + 1, AMax, BMax, answer + 1, reqTime + B[Bi], K)
        elif(Bi == BMax):
            return survey(A, B, Ai + 1, Bi, AMax, BMax, answer + 1, reqTime + A[Ai], K)
        else:
            return max(survey(A, B, Ai + 1, Bi, AMax, BMax, answer + 1, reqTime + A[Ai], K), survey(A, B, Ai, Bi + 1, AMax, BMax, answer + 1, reqTime + B[Bi], K))
        
def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    A = A
    B = B

    AMax = len(A)
    BMax = len(B)

    answer = 0
    reqTime = 0

    Ai = 0
    Bi = 0

    answer = survey(A, B, Ai, Bi, AMax, BMax, answer, reqTime, K)
    print(answer)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    AReqTime = [0]
    BReqTime = [0]

    for i in range(N):
        AReqTime.append(AReqTime[i] + A[i])
    for i in range(M):
        BReqTime.append(BReqTime[i] + B[i])

    j = M
    answer = 0

    for i in range(N + 1):
        if(AReqTime[i] > K):
            break

        while BReqTime[j] > K - AReqTime[i]:
            j = j - 1

        answer = max(i + j, answer)

    print(answer)

if __name__ == "__main__":
    main()
N,M,K=map(int, input().split())
'''
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
'''

# 再帰制限に引っかかった場合に外す
# import sys
# sys.setrecursionlimit(100000)
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)]

a = cmb(n,r)

ans=0

for i in range(K+1):
  temp=(M*(M-1)**(N-1-i)*cmb(N-1,i))%998244353
  ans+=temp

print(ans%998244353)

### FIXED CODE ###

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

MOD=998244353

ans=0
temp2=1
#temp4=(M-1)**(N-1)%MOD

def getInvs(n, MOD):
  invs = [1] * (n+1)
  for x in range(2, n+1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
  return invs

invs = getInvs(max(N+3,M-1), MOD)

Vec=[0]*N
#inv=1
#for i in range(MOD-2):
#  inv*=M-1
#  inv%=MOD

'''
for i in range(K+1):
  if i == 0:
    temp1=M
    temp1*=(M-1)**(N-1)%MOD
    temp1%=MOD
    ans+=temp1*temp2%MOD
    #print(cmb)
  else:
    temp1*=invs[M-1]%MOD
    temp2*=(N-i)*invs[i]
    temp2%=MOD
    ans+=temp1*temp2%MOD
    cmb=cmb*(N-i-1)*i*invs[i]%MOD
    #print(cmb)
'''
for i in range(N):
  if i == 0:
    temp1=M
    Vec[N-i-1]=temp1
  else:
    temp1*=(M-1)*(N-i)
    temp1*=invs[i]
    temp1%=MOD
    Vec[N-i-1]=temp1


ans=sum(Vec[:K+1])

print(ans%MOD)
N = input()
A = int(N[-3])*100 + int(N[-2])*10 + int(N[-1])
if A == 0:
    zero = 0
    print(zero)
else:
 print(1000 - A)

### FIXED CODE ###

N = input()
if len(N) >= 3:
    A = int(N[-3])*100 + int(N[-2])*10 + int(N[-1])
    if A == 0:
        print(0)
    else:
        print(1000 - A)
elif len(N) == 2:
    A = int(N[-2])*10 + int(N[-1])
    print(1000 - A)
elif len(N) == 1:
    A = int(N[-1])
    print(1000 - A)
import sys
import numpy as np

# import os
# path = os.getcwd()
# path = os.path.join(path,"input.txt")
# sys.stdin = open(path)

input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1))
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    for col in range(w[row],W+1):
        dp[row+1,col] = max(v[row]+dp[row,col-w[row]],dp[row,col])

ans = int(max(dp[N]))
print(ans)

### FIXED CODE ###

import sys
import numpy as np


input = sys.stdin.readline
N,W  = map(int,input().split())
dp = np.zeros((N+1,W+1),dtype=int)
w,v = [],[]
for _ in range(N):
    w_,v_ = map(int,input().split())
    w.append(w_)
    v.append(v_)

for row in range(N):
    dp[row+1,:w[row]] = dp[row,:w[row]]
    dp[row+1,w[row]:] = np.maximum(dp[row,w[row]:],v[row]+dp[row,:-w[row]])
print(dp[N,-1])
n=int(input())
b=list(map(int,input().split()))
a=[]
ans=b[0]
a.append(ans)
for i in range(1,n-1):
    #print('i=',i)
    if(b[i] < ans):
        a.append(b[i])
    else:
        a.append(ans)
    ans=b[i]
a.append(b[i])
print(sum(a))

### FIXED CODE ###

n=int(input())
b=list(map(int,input().split()))
a=[]
ans=b[0]
a.append(ans)
#print(n-2)
#exit()
if(n-2==0):
    print(b[0]*2)
    exit()
for i in range(1,n-1):
    if(b[i] < ans):
        a.append(b[i])
    else:
        a.append(ans)
    ans=b[i]
a.append(b[i])
print(sum(a))
n, x = map(int, input().split())
l = list(map(int, input().split()))
d = 0
i = 0
while d <= x:
    d += l[i]
    i += 1
    if i == x:
        break
print(i)

### FIXED CODE ###

n, x = map(int, input().split())
l = list(map(int, input().split()))
d = 0
s = 0
for i in range(n):
    s += l[i]
    if s > x:
        print(i+1)
        break
else:
    print(n+1)