Harryxun/stf_run huggingface dataset:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

if N==K: #全部
    ans=1
    for i in range(N):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1: #答えがマイナス
    A.sort(reverse=True)
    ans=1
    for i in range(K):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()

plus=[]
minus=[]
for i in range(N):
    if A[i]>=0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True) #5,3,1
minus.sort() #-5,-3,-1
plus_k=0
minus_k=0
if K%2==0:
    ans=1
else:
    ans=plus[0]
    plus_k=1

for _ in range(K):
    if plus_k+minus_k==K:
        break
    if plus_k==len(plus)-1:
        ans*=minus[minus_k+1]*minus[minus_k+2]%mod
        ans%=mod
        minus_k+=2
        continue
    if minus_k==len(minus)-1:
        ans*=plus[plus_k+1]*plus[plus_k+2]%mod
        ans%=mod
        plus_k+=2
        continue
    if plus[plus_k+1]*plus[plus_k+2]>minus[minus_k+1]*minus[minus_k+2]:
        ans*=plus[plus_k+1]*plus[plus_k+2]%mod
        ans%=mod
        plus_k+=2
        continue
    else:
        ans*=minus[minus_k+1]*minus[minus_k+2]%mod
        ans%=mod
        minus_k+=2
        continue
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

if N==K: #全部
    ans=1
    for i in range(N):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()
if max(A)<0 and K%2==1: #答えがマイナス
    A.sort(reverse=True)
    ans=1
    for i in range(K):
        ans*=A[i]
        ans%=mod
    print(ans)
    exit()

plus=[]
minus=[]
for i in range(N):
    if A[i]>=0:
        plus.append(A[i])
    else:
        minus.append(A[i])
plus.sort(reverse=True) #5,3,1
minus.sort() #-5,-3,-1
plus_k=0
minus_k=0
if K%2==0:
    ans=1
else:
    ans=plus[0]
    plus_k=1

for _ in range(K):
    if plus_k+minus_k==K:
        break
    if plus_k>=len(plus)-1:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
    if minus_k>=len(minus)-1:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    if plus[plus_k]*plus[plus_k+1]>minus[minus_k]*minus[minus_k+1]:
        ans*=plus[plus_k]*plus[plus_k+1]%mod
        ans%=mod
        plus_k+=2
        continue
    else:
        ans*=minus[minus_k]*minus[minus_k+1]%mod
        ans%=mod
        minus_k+=2
        continue
print(ans)
if (N % 7) % 4 == 0 or (N % 4) % 7 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
N = int(input())

for i in range((N // 4)+1):
    for j in range((N // 7)+1):
        if 4 * i + 7 * j == N:
            print("Yes")
            sys.exit()
print("No")
l=list(map(int,input().split()))
if max[l]!=l[2] and min(l)!=l[2]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

l=list(map(int,input().split()))
if max(l)!=l[2] and min(l)!=l[2]:
  print("Yes")
else:
  print("No")
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
sss = open(0).read().split()

m = {}
for s in sss:
    if s in m:
        m[s] += 1
    else:
        m[s] = 1

items = m.items()
items = list(sorted(items, key=lambda i:i[0]))
items = list(sorted(items, key=lambda i: i[1], reverse=True))

max_ = items[0][1]
i = 0
while i<len(items) and items[i][1] == max_:
    print(items[i][0])
    i+=1


### FIXED CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

n = int(input())
sss = []
for _ in range(n):
    sss.append(input())

m = {}
for s in sss:
    if s in m:
        m[s] += 1
    else:
        m[s] = 1

items = m.items()
items = list(sorted(items, key=lambda i:i[0]))
items = list(sorted(items, key=lambda i: i[1], reverse=True))

max_ = items[0][1]
i = 0
while i<len(items) and items[i][1] == max_:
    print(items[i][0])
    i+=1
N, M = [int(s) for s in input().split(' ')]
A = [int(s) for s in input().split(' ')]

task_days = sum(A)

if N < task_days:
    return -1
else:
    return N - task_days

### FIXED CODE ###

N, M = [int(s) for s in input().split(' ')]
A = [int(s) for s in input().split(' ')]

task_days = sum(A)

if N < task_days:
    print(-1)
else:
    print(N - task_days)
import sys
import decimal # 10進法に変換，正確な計算

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

def main():
    n = int(input())
    n = decimal.Decimal(n)
    if n % 2 == 0:
        print(1/decimal.Decimal(2))
        return
    
    print(((n-1)/2+1)/n)

    
    
main()

### FIXED CODE ###

import sys
import decimal # 10進法に変換，正確な計算

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

def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    count = 0
    for i in h:
        if i >= k:
            count += 1
    print(count)

    
    
main()
N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*(N*N+100) for j in range(N+10)] for i in range(N+10)]
dp[0][0][0]=1
for i in range(N):
    for j in range(N+1):
        for k in range(sum(x)+1):
            if(dp[i][j][k]!=0):
                dp[i+1][j][k]+=dp[i][j][k]
                dp[i+1][j+1][k+x[i]]+=dp[i][j][k]
print(sum(dp[N][i][i*A] for i in range(1,N+1)))

### FIXED CODE ###

N,A=map(int,input().split())
x=list(map(int,input().split()))
dp=[[[0]*2600 for j in range(N+10)] for i in range(N+10)]
dp[0][0][0]=1
for i in range(N):
    for j in range(N+1):
        for k in range(2501):
            if(dp[i][j][k]!=0):
                dp[i+1][j][k]+=dp[i][j][k]
                dp[i+1][j+1][k+x[i]]+=dp[i][j][k]
print(sum(dp[N][i][i*A] for i in range(1,N+1)))
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

output:
yes
yes
no

"""

import sys


def assign_color():
    _color = 1
    for v in range(vertices):
        if color[v] == -1:
            graph_dfs(v, _color)
            _color += 1
    return None


def graph_dfs(vertex, _color):
    vertices_stack = list()
    vertices_stack.append(vertex)
    _color[vertex] = _color

    while vertices_stack:
        current_vertex = vertices_stack.pop()
        for v in adj_table[current_vertex]:
            if _color[v] == -1:
                _color[v] = _color
                vertices_stack.append(v)
    return None


def solve():
    for relation in relation_info:
        key, value = map(int, relation)
        adj_table[key].append(value)
        adj_table[value].append(key)

    assign_color()

    # print(adj_list)
    for question in questions:
        start, target = map(int, question)
        if color[start] == color[target]:
            print("yes")
        else:
            print("no")
    return color


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices, relations = map(int, _input[0].split())

    relation_info = map(lambda x: x.split(), _input[1:relations + 1])

    q_num = int(_input[relations + 1])
    questions = map(lambda x: x.split(), _input[relations + 2:])

    adj_table = tuple([] for _ in range(vertices))
    color = [-1] * vertices
    ans = solve()

### FIXED CODE ###

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

"""
input:
10 9
0 1
0 2
3 4
5 7
5 6
6 7
6 8
7 8
8 9
3
0 1
5 9
1 3

output:
yes
yes
no

"""

import sys


def assign_color():
    v_color = 0
    for v in range(v_num):
        if color[v] == -1:
            graph_dfs(v, v_color)
            # use int as color to represent different connected groups
            v_color += 1
    return None


def graph_dfs(current, v_color):
    stack = list()
    stack.append(current)
    color[current] = v_color

    while stack:
        current = stack.pop()
        for adj in adj_table[current]:
            if color[adj] == -1:
                color[adj] = v_color
                stack.append(adj)
    return None


def solve():
    for edge in edges:
        source, target = map(int, edge)
        adj_table[source].append(target)
        adj_table[target].append(source)

    assign_color()

    for question in questions:
        q_source, q_target = map(int, question)
        if color[q_source] == color[q_target]:
            print("yes")
        else:
            print("no")

    return color


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    v_num, r_num = map(int, _input[0].split())

    edges = map(lambda x: x.split(), _input[1:r_num + 1])

    q_num = int(_input[r_num + 1])
    questions = map(lambda x: x.split(), _input[r_num + 2:])

    adj_table = tuple([] for _ in range(v_num))
    color = [-1] * v_num
    ans = solve()
S = input()
h = S / 3600
m = h % 3600 / 60
s = m % 60 /60

print(h,m,s,sep = ':')

### FIXED CODE ###

S = int(input())
h = int(S / 3600)
m = int(S % 3600 / 60)
s = int(S % 60)
print(h, m, s, sep=':')
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,m,k = map(int,input().split())
nm = n*m%(10**9+7)
k = k%(10**9+7)
a = (cmb(nm-2,k-2,mod)%(10**9+7))*(nm*(m*(n**2-1)+n*(m**2-1)))//6
print(a%(10**9+7))

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,m,k = map(int,input().split())
nm = n*m%(10**9+7)
k = k%(10**9+7)
a = (cmb(nm-2,k-2,mod)%(10**9+7))*(nm*(m*(n**2-1)+n*(m**2-1)))//6
print(a%(10**9+7))
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

if max(c) < 0:
    res = max(c)
else:
    res = 0

for i in range(n):
    score = []
    s = 0
    pos = i
    visited = [False] * n
    loop = 0
    while True:
        if visited[pos]:
            break

        visited[pos] = True
        s += c[p[pos]-1]
        score.append(s)
        pos = p[pos] - 1
        loop += 1

    if k < loop:
        res = max(res, max(score[:k]))
    elif score[-1] <= 0:
        res = max(res, max(score))
    else:
        res = max(res, score[-1] * (k // loop) + max(score[:k%loop]), score[-1] * (k // loop - 1) + max(score))

print(res)

### FIXED CODE ###

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

if max(c) < 0:
    res = max(c)
else:
    res = 0

for i in range(n):
    score = []
    s = 0
    pos = i
    visited = [False] * n
    loop = 0
    while True:
        if visited[pos]:
            break

        visited[pos] = True
        s += c[p[pos]-1]
        score.append(s)
        pos = p[pos] - 1
        loop += 1

    if k < loop:
        res = max(res, max(score[:k]))
    elif score[-1] <= 0:
        res = max(res, max(score))
    elif k % loop == 0:
        res = max(res, score[-1] * (k // loop), score[-1] * (k // loop - 1) + max(score))
    else:
        res = max(res, score[-1] * (k // loop) + max(score[:k%loop]), score[-1] * (k // loop - 1) + max(score))

print(res)
k=int(input())
s=input()
if lens(s)>k:
  print(s[:k]+"..")
else:
  print(s)
s[]
s[5:]

### FIXED CODE ###

#input the K and S string
#using another new variable to count the length of string
#then compare the value with the string
#if string less than the value just pring the string S
#if the length of string more than the value
#cut the string using while loop then print ... at the end
#program end

K = int(input())  #O(1)
S = input() #O(1)
value=len(S)    #O(1)

if value <= K: 
    print(S)    #O(1)
elif value > K : 
    x=0     #O(1)
    while x<K: 
        print((S[x]),end=(""))  #O(1)
        x+=1
    print("...")   #O(1)
from fractions import gcd
from functools import reduce
N, M = map(int, input().split())
A = list(map(int, input().split()))
def lcm_(x, y):
    x_ = x // 2
    y_ = y // 2
    return x_ * y_ // gcd(x_, y_)
a = reduce(lcm_, A)
print(M//a - M//(2*a))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
N, M = map(int, input().split())
A = list(map(int, input().split()))
AA = list(map(lambda x: x//2, A))
def lcm(x, y):
    return x * y // gcd(x, y)
b0 = AA[0]&-AA[0]
for a in AA[1:]:
    if b0 != a&-a:
        print(0)
        break
else:
    a = reduce(lcm, AA)
    print(M//a - M//(2*a))
n = int(input())
price = [int(input()) for _ in range(n)]
print(int(sum(price) - max(price) / 2))

### FIXED CODE ###

d = int(input())
s = 'Christmas' + ' Eve' * (25 - d)
print(s)
n = int(input())
a = [int(i) for i in input().split()]

val = []

for i in range(n):
    val.append(a[i]-i)

val.sort()
#print(val)

#idx = [(val[0],0)]
idx = []
cnt = 1
for i in range(n-1):
    if val[i] == val[i+1]:
        #cnt += 1
        if i == n-2:
            idx.append((val[i],i+2))
        continue
    else:
        idx.append((val[i],i+1))
        #cnt = 1
        
ans_val = 0

for i in range(len(idx)):
    if idx[i][1] >= (n) // 2:
        ans_val = idx[i-1][0]

#print(ans_val)
#exit()
     
ans = 0
ans2 = 0
ans3 = 0
for i in range(n):
    ans += abs(a[i]-ans_val-i)
    ans2 += abs(a[i]-ans_val-i+1)
    ans3 += abs(a[i]-ans_val-i-1)
    

print(min(ans,ans2,ans3))

### FIXED CODE ###

n = int(input())

if n % 2 == 0:
    print(n)
else:
    print(n*2)
from collections import Counter
n = int(input())
A = Counter(list(input()))
B = Counter(list(input()))
C = Counter(list(input()))
ans = []
for key,value in A.items():
  ans.append(key*min(value,B[key],C[key]))
print(join(sorted(ans)),end="")

### FIXED CODE ###

from collections import Counter
n=int(input())
s=Counter(input())
for i in range(n-1):
    s&=Counter(input())
print("".join(sorted(s.elements())))
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
X = str(input())
start_mod = X.count("1")
if start_mod == 1:
  for i in range(n):
    if X[i] == "1":
      key = 1
else: key = -1
# start_number = int(X,2)
def bin_to_int(n,binstr,mod):
  retval = 0
  for i in range(n-1,-1,-1):
    retval += (pow(2,n-1-i,mod) if binstr[i] == "1" else 0)
    retval %= mod
  return retval
start_number_plus = bin_to_int(n,X,start_mod+1)
start_number_minus = bin_to_int(n,X,start_mod-1)
# print(start_number_plus,start_number_minus,"debug")
for i in range(n):
  if i == key:print(0);continue
  if X[i] == "1":
    now_mod = start_mod - 1
    now_number = (start_number_minus - pow(2,n-1-i,now_mod))%now_mod
      
  else:
    now_mod = start_mod + 1
    now_number = (start_number_plus + pow(2,n-1-i,now_mod))%now_mod
  # print(i,now_number,now_mod,"debug")
  ci = 1
  while now_number != 0:
    # print(now_number,now_mod)
    now_mod = bin(now_number).count("1")
    now_number %= now_mod
    ci += 1
  print(ci)

### FIXED CODE ###

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
X = str(input())
start_mod = X.count("1")
if start_mod == 1:
  for i in range(n):
    if X[i] == "1":
      key = i
else: key = -1

def bin_to_int(n,binstr,mod):
  retval = 0
  for i in range(n-1,-1,-1):
    retval += (pow(2,n-1-i,mod) if binstr[i] == "1" else 0)
    retval %= mod
  return retval

start_number_plus = bin_to_int(n,X,start_mod+1)
if key == -1:
  start_number_minus = bin_to_int(n,X,start_mod-1)
# print(start_number_plus,start_number_minus,"debug")

# print(key,"debug3")
for i in range(n):
  if i == key:print(0);continue
  if X[i] == "1":
    now_mod = start_mod - 1
    now_number = (start_number_minus - pow(2,n-1-i,now_mod))%now_mod
      
  else:
    now_mod = start_mod + 1
    now_number = (start_number_plus + pow(2,n-1-i,now_mod))%now_mod
  # print(i,now_number,now_mod,"debug")
  ci = 1
  while now_number != 0:
    # print(now_number,now_mod)
    now_mod = bin(now_number).count("1")
    now_number %= now_mod
    ci += 1
  print(ci)
n,m=map(int, input().split())
l=[input().split() for i in range(m)]
m={}
for j in range(len(l)):
    if l[j][0] not in m.keys():
        m[l[j][0]]=[]
    m[l[j][0]].append(l[j][1])
lab=[0]*(n+1)
for k in m.keys():
    m[k] = sorted(m[k], reverse=False)
    p='0'*(6-len(k))+k
    for h in range(len(m[k])):
        q='0'*(6-len(str(h+1)))+str(h+1)
        key=l.index([k,m[k][h]])
        lab[key]=p+q
for v in lab:
    print(v)


### FIXED CODE ###

n,m=map(int, input().split())
l = [[int(i) for i in input().split()] for i in range(m)]

for i in range(m):
    l[i].append(i)
l = sorted(l,key=lambda x: (x[0],x[1]))

l[0].append(1)
for i in range(1,m):
    if l[i][0]!=l[i-1][0]:
        l[i].append(1)
    else:
        l[i].append(l[i-1][3]+1)

for i in range(m):
    l[i].append(str(l[i][0]).zfill(6) + str(l[i][3]).zfill(6))

l=sorted(l,key=lambda x:(x[2]))

for i in range(m):
    print(l[i][4])
#include<bits/stdc++.h>
using namespace std;

int main(){
    int X;
    cin >> X;
    if ((X == 3) || (X == 5) || (X == 7)){
        cout << "YES" << endl;
    }else {
        cout << "NO" << endl;
    }
}

### FIXED CODE ###

x = int(input())
if (x == 7) or (x == 5) or (x == 3):
  print("YES")
else:
  print("NO")
n, m = map(int, input().split())
p_li, s_li = [], []
for _ in range(m):
    p, s = input().split()
    p_li.append(int(p))
    s_li.append(s)

ac = [0] * n
wa = [0] * n
for i in range(m):
    p, s = p_li[i] - 1, s_li[i]
    if s == 'AC':
        ac[p] += 1
    elif ac[p] == 0:
        wa[p] += 1
    else:
        continue
n_ac, n_wa = 0, 0
for i in range(n):
    if ac[i] != 0:
        n_ac += 1
        n_wa += wa[i]
print('{} {}'.format(ans[0], ans[1]))

### FIXED CODE ###

n, m = map(int, input().split())
p_li, s_li = [], []
for _ in range(m):
    p, s = input().split()
    p_li.append(int(p))
    s_li.append(s)

ac = [0] * n
wa = [0] * n
for i in range(m):
    p, s = p_li[i] - 1, s_li[i]
    if s == 'AC':
        ac[p] += 1
    elif ac[p] == 0:
        wa[p] += 1
    else:
        continue
n_ac, n_wa = 0, 0
for i in range(n):
    if ac[i] != 0:
        n_ac += 1
        n_wa += wa[i]
print('{} {}'.format(n_ac, n_wa))
import bisect


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]
    next_robot_list = [-1] * N

    def search_next_robot(r):
        if next_robot_list[r] >= 0:
            return next_robot_list[r]
        if r == N - 1:
            next_robot_list[r] = N
            return N
        if X[r] + D[r] <= X[r + 1]:
            next_robot_list[r] = r + 1
            return r + 1
        next_r_to = bisect.bisect_left(X, X[r] + D[r])
        ret = next_r_to
        for next_r in range(r + 1, next_r_to):
            ret = max(ret, search_next_robot(next_r))
        next_robot_list[r] = ret
        return ret

    for n in range(N):
        search_next_robot(n)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        cnt[next_robot_list[n]] += cnt[n]
        cnt[next_robot_list[n]] %= MOD
    print(cnt[N])


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
import sys


sys.setrecursionlimit(10**6)
INF = 10**6


class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [- INF] * (2 * N - 1)

    def update(self, i, x):
        n = self.N + i - 1
        self.data[n] = x
        while n > 0:
            n = (n - 1) // 2
            self.data[n] = max(self.data[2 * n + 1], self.data[2 * n + 2])        

    def elem(self, i):
        return self.data[self.N + i - 1]

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return - INF
        if a <= l and r <= b:
            return self.data[k]
        val_left = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
        val_right = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
        return max(val_left, val_right)

    def query(self, a, b):
        return self._query(a, b, 0, 0, self.N)


def main():
    MOD = 998244353
    N = int(input())
    robot_list = [list(map(int, input().split())) for _ in range(N)]
    robot_list.sort()  # x座標の昇順でソート
    X = [robot[0] for robot in robot_list]
    D = [robot[1] for robot in robot_list]

    PW_N = 1
    while PW_N < N:
        PW_N *= 2
    next_robot_tree = SegTree(PW_N)
    next_robot_tree.update(N - 1, N)
    for n in range(N - 2, - 1, - 1):
        if X[n] + D[n] <= X[n + 1]:
            next_robot_tree.update(n, n + 1)
        else:
            next_robot = bisect.bisect_left(X, X[n] + D[n])
            next_robot = next_robot_tree.query(n, next_robot)
            next_robot_tree.update(n, next_robot)

    cnt = [0] * (N + 1)
    cnt[0] = 1
    for n in range(N):
        cnt[n + 1] += cnt[n]
        cnt[n + 1] %= MOD
        next_robot = next_robot_tree.elem(n)
        cnt[next_robot] += cnt[n]
        cnt[next_robot] %= MOD
    print(cnt[N])


if __name__ == '__main__':
    main()
n,m=input().split()
h_list = []
h_list = input().split(" ")
result =[True]*n
count = 0
for i in range(int(m)):
    temp1,temp2=input().split()
    if h_list[int(temp1)-1] < h_list[int(temp2)-1]:
        result[int(temp1)-1] = False
    elif h_list[int(temp1)-1] == h_list[int(temp2)-1]:
        result[int(temp1) - 1] = False
        result[int(temp2) - 1] = False
    else:
        result[int(temp2)-1] = False
for i in range(int(n)):
    if(result[i]==True):
        count += 1
print(count)

### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
p = [0 for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    if h[a-1] >= h[b-1]:
        p[b-1] = -1
    if h[a-1] <= h[b-1]:
        p[a-1] = -1
print(p.count(0))
X = input()

print(X // 500 * 1000 + X % 500 // 5 * 5)

### FIXED CODE ###

X = int(input())

print(X // 500 * 1000 + X % 500 // 5 * 5)
import math
def combinations(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))

n, k = map(int, input().split())
for i in range(k):
    print(combinations(n - k + 1, i + 1) * combinations(k - 1, i) % (10 ** 9 + 7))


### FIXED CODE ###

import math
def combinations(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))
    
n, k = map(int, input().split())
if k == 1:
    print(n - k + 1)
else:    
    for i in range(k):
        if n - k < i:
            print("0")
        else:
            print(combinations(n - k + 1, i + 1) * combinations(k - 1, i) % (10 ** 9 + 7))