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

def main():
    import sys
    input = sys.stdin.readline

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

    ans = [0] * p
    for i, a in enumerate(A):
        if not a:
            continue
        ans[-1] += 1
        for j in range(p):
            ans[j] = (ans[j] - pow(i, j, p))%p
    ans.reverse()
    print(*ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

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

    ans = [0] * p
    for i, a in enumerate(A):
        if not a:
            continue
        ans[-1] += 1
        ij = 1
        ans[0] = (ans[0] - ij)%p
        for j in range(1, p):
            ij = (ij * i)%p
            ans[j] = (ans[j] - ij)%p
    ans.reverse()
    print(*ans)


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

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
ans = set(range(1, N + 1))
for lr in LR:
  ans = ans & set(range(lr[0], lr[1] + 1))
  
print(len(ans))

### FIXED CODE ###

N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
l = 0
r = 100001
for lr in LR:
  l = max(lr[0], l)
  r = min(r, lr[1])
  
print(r - l + 1 if r - l >= 0 else 0)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
for i in range(len(a)):
    a1=a.copy()
    a1.pop(i)
    c=[0]+a1+[0]
    b=[]
    for i in range(len(c)-1):
        b.append(abs(c[i]-c[i+1]))
    print(sum(b))

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
b=[]
c=[0]+a+[0]
for i in range(len(c)-1):
    b.append(c[i+1]-c[i])
sumb=sum([abs(i) for i in b])
 
for i in range(n):
    print(sumb-abs(b[i])-abs(b[i+1])+abs(b[i]+b[i+1]))
### BUGGY CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List
import array
import numpy as np

# from typing import Dict
from typing import Tuple

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList: array[Cod] = []
    for i in range(M):
        args = input().split()
        codList.append((int(args[0]), int(args[1])))

    columnSumList: array[int] = np.zeros(W, dtype="int32")
    rowSumList: array[int] = np.zeros(H, dtype="int32")

    maxColumnSum = 0
    maxColumIndexList: array[int] = []
    maxRowSum = 0
    maxRowIndexList: array[int] = []
    for item in codList:
        columnSum = columnSumList[item[1] - 1] + 1
        if columnSum > maxColumnSum:
            maxColumnSum = columnSum
            maxColumIndexList = [item[1]]
        elif columnSum == maxColumnSum:
            maxColumIndexList.append(item[1])

        rowSum = rowSumList[item[0] - 1] + 1
        if rowSum > maxRowSum:
            maxRowSum = rowSum
            maxRowIndexList = [item[0]]
        elif rowSum == maxRowSum:
            maxRowIndexList.append(item[0])

        columnSumList[item[1] - 1] = columnSum
        rowSumList[item[0] - 1] += 1

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if (row, column) in codList:
                continue
            else:
                print(result)
                return

    print(result - 1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

# from typing import Optional
from typing import List

# from typing import Dict
from typing import Tuple
from typing import Set

# from typing import Sequence

Cod = Tuple[int, int]


def main():
    args = input().split()
    H = int(args[0])
    W = int(args[1])
    M = int(args[2])

    codList = {}
    columnSumList: List[int] = [0] * W
    rowSumList: List[int] = [0] * H
    for i in range(M):
        h, w = map(lambda x: int(x), input().split())
        item = (h, w)
        codList.setdefault(h, {})
        codList[h][w] = item
        columnSumList[w - 1] += 1
        rowSumList[h - 1] += 1

    maxColumnSum = max(columnSumList)
    maxColumIndexList = [i for i, x in enumerate(columnSumList) if x == maxColumnSum]
    maxRowSum = max(rowSumList)
    maxRowIndexList = [i for i, x in enumerate(rowSumList) if x == maxRowSum]

    result = maxColumnSum + maxRowSum
    for row in maxRowIndexList:
        for column in maxColumIndexList:
            if row + 1 in codList and column + 1 in codList[row + 1]:
                continue
            else:
                print(result)
                return

    print(result - 1)


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

N = int(input())
a  = list(input().split())

for i in range(1, N+1):
    print(a.count(str(i)))

### FIXED CODE ###

from collections import Counter
N = int(input())
a  = list(input().split())
fact_count = dict(Counter(a))
for i in range(1, N+1):
    try:
        print(fact_count[str(i)])
    except:
        print(0)
### BUGGY CODE ###

#DP B
import sys
N, K = map(int, sys.stdin.readline().split())
H = list(map(int, sys.stdin.readline().split()))

dp = [0 for _ in range(N)]
#print(dp)
#print(H)
dp[1] = abs(H[1]-H[0])
#print(dp)

for i in range(2, N):
    for k in range(1, K+1):
        if i-k>=0:
            tmp = abs(H[i]-H[i-k]) + dp[i-k]
            if dp[i] ==0 or tmp < dp[i]:
                dp[i] = tmp
    #print(dp)
print(dp[-1])

### FIXED CODE ###

import sys
n, K = map(int, sys.stdin.readline().split())
H = list(map(int, sys.stdin.readline().split()))

p = [float('inf') for _ in range(n)]
p[0] = 0
for i in range(1, n):
    for k in range(1, K+1):
        if i-k >=0:
            tmp = abs(H[i]-H[i-k]) + p[i-k]
            if p[i] > tmp:
                p[i] = tmp

print(p[-1])
### BUGGY CODE ###

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)


for i in set(lis[-1]):
  if i in set(lis[0]):
    print('POSSIBLE')
    exit()
  
print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
 
lis = [[] for i in range(n)] #なぜか知らんけど[[]]*nじゃだめらしい
 
for i in range(m):
  a,b = map(int,input().split())
  lis[a-1].append(b-1)
  lis[b-1].append(a-1)
 
 
if set(lis[-1]).isdisjoint(set(lis[0])):
    print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

from math import sqrt
cash = {}
def isprime(n):
    if n in cash:
        return cash[n]
    for i in range(3, int(sqrt(n)+1))[0::2]:
        if n % i == 0:
            cash[n] = 0
            return 0
    cash[n] = 1
    return 1

from sys import stdin
for i in stdin:
    print(sum(isprime(n) for n in range(2, int(i)+1)[1::2]) + 1)

### FIXED CODE ###

from math import sqrt,floor
from sys import stdin

def cntPrime(n):
    mx = sqrt(n)
    if n % 2 == 0:
      l = [0, 1] + [1, 0] * (int(n/2) - 1)
    else:
      l = [0, 1] + [1, 0] * (int(n/2) - 1) + [1]
    c = 3
    while c < mx:
        for k in range(c*2, n+1, c):
            l[k-1] = 0
        c = l[(c+1):].index(1) + c +2
        while c % 2 == 0:
            c = l[(c+1):].index(1) + c +2
    return l
t = cntPrime(1000000)
for n in stdin:
    n = int(n)
    print(sum(t[:n]))
### BUGGY CODE ###

from sys import stdin

def main():
    n = int(input())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    m = 10 ** 9 + 7
    s = 0
    for i in range(len(A)-1):
        for j in range(i+1,len(A)):
            aa = A[i]% m
            bb = A[j]% m
            ans = aa * bb
            s += ans

    s = s % m
    print(s)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin

def main():
    n = int(input())
    A = [int(x) for x in stdin.readline().rstrip().split()]

    m = 10 ** 9 + 7
    s = 0
    b_sum = sum(A)
    for i in range(len(A)-1):
        b_sum = b_sum -A[i]
        rest = b_sum % m
        ans = A[i] * rest % m
        s += ans

    s = s % m
    print(s)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


N = int(input())
A = [int(input()) for i in range(N)]
mod = 998244353
ans = pow(3, N, mod)
sum_A = sum(A)
dp = dp_table(N, sum_A + 1)
# dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

# init
dp[0][A[0]] = 1
dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

# init2
dp2 = dp_table(N, sum_A+1)  # ある二色でsum_Aを等分するパターンを数える
dp2[0][A[0]] = 1
dp2[0][0] = 1  # 今度は片方に集中したパターン

# dp
for i in range(1, N):
    for length in range(0, sum_A + 1):
        # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
        if length >= A[i]:
            dp[i][length] = dp[i - 1][length - A[i]] + dp[i - 1][length] * 2
        else:
            dp[i][length] = dp[i-1][length]*2
        dp[i][length] %= mod
        if length >= A[i]:
            dp2[i][length] = dp2[i - 1][length - A[i]] + dp2[i - 1][length]
        else:
            dp2[i][length] = dp2[i-1][length]
        dp2[i][length] %= mod
# print(sum(dp[N-1][sum_A//2]))
# print(dp)
ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
if sum_A % 2 == 0:
    ans += 3*dp2[N-1][sum_A//2]
print(ans % mod)


### FIXED CODE ###


def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve():
	N, Q = MAP()
	ab = [LIST() for _ in range(N-1)]
	tree = defaultdict(list)
	par = [-1]*N
	par[0] = 0
	for a, b in ab:
		tree[a-1].append(b-1)
		tree[b-1].append(a-1)
	search = []
	searched = [0] * N
	searched[0] = 1
	for child in tree[0]:
		par[child] = 0
		search.append(child)

	while search:
		x = search.pop(0)
		for child in tree[x]:
			if searched[child] == 0:
				par[child] = x
				searched[x] = 1
				search.append(child)

	# def parent(n):
	# 	for child in tree[n]:
	# 		if par[child] == -1:
	# 			par[child] = n
	# 			parent(child)
	# parent(0)
	# print(par)
	px = [LIST() for _ in range(Q)]

	counter = defaultdict(int)  # まとめる
	for p, x in px:
		counter[p-1] += x

	ans = [-1] * N  # 答え入れる
	ans[0] = counter[0]

	search = []
	searched = [0] * N
	searched[0] = 1
	for child in tree[0]:
		par[child] = 0
		search.append(child)

	while search:
		x = search.pop(0)
		ans[x] = counter[x] + ans[par[x]]
		for child in tree[x]:
			if searched[child] == 0:
				par[child] = x
				searched[x] = 1
				search.append(child)

	# def DFS(n):
	# 	if n != 0:
	# 		ans[n] = counter[n] + ans[par[n]]
	# 	for child in tree[n]:
	# 		if ans[child] == -1:
	# 			DFS(child)

	# DFS(0)
	print(*ans, sep=" ")

if  __name__ == "__main__":
	solve()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve():
	N, Q = MAP()
	ab = [LIST() for _ in range(N-1)]
	tree = defaultdict(list)
	par = [-1]*N
	par[0] = 0
	for a, b in ab:
		tree[a-1].append(b-1)
		tree[b-1].append(a-1)
		par[b-1] = a-1

	px = [LIST() for _ in range(Q)]

	ans = [0] * N  # 答え入れる

	for p, x in px:
		ans[p-1] += x

	
	for i in range(1, N):
		ans[i] += ans[par[i]]

	print(*ans, sep=" ")

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

import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
A = list(sorted(A))
q = deque(A)
ans = 0
while q:
  t = q.popleft()
  cnt = q.count(t)
  if t == 1:
    if cnt == 0:
      print(1)
      sys.exit()
    else:
      print(0)
      sys.exit()
  if cnt == 0:
    ans += 1
  count = 0
  for j in range(len(q)):
    if q[j] % t == 0:
      count +=1
      q.remove(q[j])
      q.appendleft(1)
  for i in range(count):
    q.remove(1)
print(ans)
    

### FIXED CODE ###

import sys 
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@jit(cache=True)
def solve(A):
  count = np.zeros(10**6+10)
  for x in A:
    if count[x] > 1:
      continue
    count[::x] += 1
  ans = 0
  for x in A:
    ans += count[x] == 1
  return ans

N = int(readline())
A = list(map(int,readline().split()))
A = np.array(A)
print(solve(A))
### BUGGY CODE ###


import sys
input = sys.stdin.readline

def update(index, value, bit):
  #print('update', index, value)
  while index < len(bit):
    #print('update', index)
    bit[index] += value
    index += index & -index
  #print('done')
    
def cumsum(index, bit):
  ans = 0
  while index > 0:
    #print('cumsum', index)
    ans += bit[index]
    index -= index & -index
  #print('done', ans)
  return ans

def main():
  N, q = [int(x) for x in input().split()]
  C = [int(x)-1 for x in input().split()]
  Q = []
  for _ in range(q):
    Q.append(tuple(int(x)-1 for x in input().split()[::-1]))
  I = sorted(range(q), key=Q.__getitem__)
  #print(I, Q)
  leftmost = [-1] * N
  bit = [0] * (N+1)
  prev = -1
  ans = [0] * q
  for i in I:
    r, l = Q[i]
    #print(i, r, l)
    for x in range(prev+1, r+1):
      if leftmost[C[x]] >= 0:
        update(leftmost[C[x]] + 1, -1, bit)
      leftmost[C[x]] = x
      update(x + 1, 1, bit)
    prev = r
    #print(i, r, l)
    #print(C)
    #print([cumsum(i, bit) for i in range(1, N+1)])
    ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
  for a in ans:
    print(a)
  

main()

### FIXED CODE ###


import sys
input = sys.stdin.readline

def update(index, value, bit):
  #print('update', index, value)
  while index < len(bit):
    #print('update', index)
    bit[index] += value
    index += index & -index
  #print('done')
    
    
def cumsum(index, bit):
  ans = 0
  while index > 0:
    #print('cumsum', index)
    ans += bit[index]
    index -= index & -index
  #print('done', ans)
  return ans
  

def main():
  N, q = [int(x) for x in input().split()]
  C = [int(x)-1 for x in input().split()]
  Q = []
  for i in range(q):
    l, r =  [int(x)-1 for x in input().split()]
    Q.append((i, l, r))
  Q.sort(key=lambda x: x[2])
  leftmost = [-1] * N
  bit = [0] * (N+1)
  prev = -1
  ans = [0] * q
  for i, l, r in Q:
    #print(i, r, l)
    to_update = {}
    for x in range(prev+1, r+1):
      to_update[C[x]] = x
    for c, x in to_update.items():
      if leftmost[c] >= 0:
        update(leftmost[c] + 1, -1, bit)
      leftmost[c] = x
      update(x + 1, 1, bit)
    prev = r
    #print(i, r, l)
    #print(C)
    #print([cumsum(i, bit) for i in range(1, N+1)])
    ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
    
  for a in ans:
    print(a)
  

main()
### BUGGY CODE ###

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

count = 1
for i in range(1, N):
    if(P[1] <= P[0]):
        P.pop(0)
        count += 1
    else:
        P.pop(1)


print(count)


### FIXED CODE ###

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

count = 1
d = P[0]
for i in range(N - 1):
    if (d > P[i + 1]):
        d = min(P[i], P[i + 1])
        count += 1

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

S = input()

def ctoi(c):
    return ord(c) - ord('a')

cums = [0]
for c in S:
    cums.append(cums[-1] ^ (1<<ctoi(c)))
if cums[-1] == 0:
    print(1)
    exit()

masks = [1<<k for k in range(26)]
dp = {0:0}
for i,b in enumerate(cums):
    for m in masks:
        msk = b^m
        if msk in dp:
            if b in dp:
                dp[b] = min(dp[b], dp[msk]+1)
            else:
                dp[b] = dp[msk]+1
print(dp[cums[-1]])

### FIXED CODE ###

def ctoi(c):
    return ord(c) - ord('a')

def solve(s):
    masks = [1<<k for k in range(26)]
    cums = [0]
    for c in s:
        cums.append(cums[-1] ^ masks[ctoi(c)])
    if cums[-1] == 0:
        print(1)
        exit()

    dp = {0:0}
    for b in cums:
        for m in masks:
            msk = b^m
            if msk in dp:
                if b in dp:
                    dp[b] = min(dp[b], dp[msk]+1)
                else:
                    dp[b] = dp[msk]+1
    return dp[cums[-1]]

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

s = list(input())
n = int(input())
import numpy as np
import collections
s = np.array(s)
s = collections.deque(s)
L = []
for i in range(n):
    L = (list(map(str,input())))
    #print(L)
    if len(L) >1:
        if int(L[2]) == 1:
            #print(s)
            s = np.append(L[4],s)
        elif int(L[2]) == 2:
            s = np.append(s,L[4])
    
    elif len(L) ==1:
        s = np.flipud(s)
        
print("".join(s))

### FIXED CODE ###

from collections import deque
s = input()
s = deque(s)
n = int(input())
cnt = False
for i in range(n):
  L = input()
  if len(L) == 1:
    cnt  ^=1 
  else:
    a,b,c = L.split()
    if cnt:
      if b == "1":
        s.append(c)
      else:
        s.appendleft(c)
    else:
      if b == "1":
        s.appendleft(c)
      else:
        s.append(c)
if cnt:
    s = reversed(s)
    print("".join(s))
else:
    print("".join(s))
### BUGGY CODE ###

L, N = (int(i) for i in input().split())
X = [int(input()) for _ in range(N)]
X.insert(0, 0)

def f(L, N, X, p, l, r, d_l):
    w = 0
    for _ in range(N - (l + r)):
        if d_l:  # L
            l += 1
            w += X[l] - p
            p = X[l]
            d_l = False
        else:  # R
            r += 1
            w += L - X[-r] + p
            p = X[-r] - L
            d_l = True
    return w

X_c = [L - i for i in X]

max_l = max(X[i] + f(L, N, X, X[i], i, 0, False) for i in range(1, N+1))
max_r = max(X_c[-i] + f(L, N, X, -X_c[-i], 0, i, True) for i in range(1, N+1))
print(max(max_l, max_r))


### FIXED CODE ###

import math

L, N = (int(i) for i in input().split())
X = [int(input()) for _ in range(N)]
X.insert(0, 0)

X_r = [L - i for i in reversed(X)]
X_r.insert(0, 0)
X_r.pop()

def lsum(l):
    s = 0
    for i in l:
        s += i
        yield s

X_sum = list(lsum(X))
X_r_sum = list(lsum(X_r))

def f_l(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_sum[a] + X_r_sum[a + n] + X_r_sum[a + n - 1] - 2 * X_r_sum[n] + p
    else:
        return X_sum[a+1] + X_sum[a] + 2 * X_r_sum[a + n] - 2 * X_r_sum[n] + p


def f_r(p, n):
    N_tmp = N - n
    a = N_tmp // 2
    if N_tmp == 0:
        return 0
    elif N_tmp % 2 == 0:
        return 2 * X_r_sum[a] + X_sum[a + n] + X_sum[a + n - 1] - 2 * X_sum[n] + p
    else:
        return X_r_sum[a+1] + X_r_sum[a] + 2 * X_sum[a + n] - 2 * X_sum[n] + p

max_l = max(X[i] + f_r(X[i], i) for i in range(1, N+1))
max_r = max(X_r[i] + f_l(X_r[i], i) for i in range(1, N+1))

print(max(max_l, max_r))
### BUGGY CODE ###

from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()
    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans *= p.pop()

    if len(p) + len(n) < k:
        print(0)
        exit()

    q = PriorityQueue()

    n = n[::-1]
    for i in range(len(n)//2):
        q.put(-n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.put(-p[2*i]*p[2*i+1])

    cnt = 0
    while cnt < k:
        ans = ans * (-q.get()) % mod
        cnt += 2

    print(ans % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from queue import PriorityQueue
import sys
from collections import defaultdict
readline = sys.stdin.buffer.readline
# sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


mod = 10**9+7


def prod(l):
    ret = 1
    for e in l:
        e %= mod
        ret = (ret*e) % mod

    return ret


def main():
    n, k = geta(int)
    a = list(geta(int))

    p, n, z = [], [], 0
    for ai in a:
        if ai > 0:
            p.append(ai)
        elif ai < 0:
            n.append(-ai)
        else:
            z += 1

    ans = 1
    p.sort()
    n.sort()
    if k & 1 == 1:
        if len(p) == 0:
            if z > 0:
                print(0)
                exit()
            else:
                print(-prod(n[0:k]) % mod)
                exit()
        else:
            k -= 1
            ans = p.pop() % mod

    if len(p) + len(n) < k:
        print(0)
        exit()

    if len(n) & 1 == 1 and (len(p) + len(n) == k):
        if z > 0:
            print(0)
            exit()
        else:
            print(-prod(p) * prod(n) % mod)
            exit()

    q = []

    n = n[::-1]
    for i in range(len(n)//2):
        q.append(n[2*i]*n[2*i+1])

    p = p[::-1]
    for i in range(len(p)//2):
        q.append(p[2*i]*p[2*i+1])

    q.sort(reverse=True)

    ans = ans * (prod(q[:k//2])) % mod

    print(ans % mod)


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

N = int(input())
P = list(map(int, input().split(" ")))
s = 1
for i in range(1,N):
    for j in range(i):
        if P[j] > P[i]:
            if i == j+1:
                s += 1
        else:
            break
print(s)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split(" ")))
cnt = 0
S = P[0]
for i in range(N):
    if S >= P[i]:
        cnt += 1
    S = min(S, P[i])

print(cnt)