Harryxun/stf_run huggingface dataset:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M)]
    A[0] = X

    start = N
    end = N

    cnt = [0 for i in range(M)]
    cnt[X] = 0

    for i in range(1,M*2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i

    # print(A)

    # print(start,end)
    # print(A[start],temp)

    L = end - start + 1

    if start != N:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
    else:
        straight = [0]

    if start != -1:
        loop = [0 for i in range(L)]

    if start != N:
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]

    # print(straight)
    # print(loop)

    res = 0

    if start != 0:
        if N >= start:
            res += straight[-1]
            N -= start
        else:
            res += straight[N-1]
            N = 0


    if start != N:
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8[:],i8[:],i8,i8,i8))
def SerchLoop(M,A,cnt,start,end,temp):
    for i in range(1,M+2):
        temp = A[i-1] ** 2
        temp %= M
        if cnt[temp] != 0:
            start = cnt[temp]
            end = i - 1
            break
        A[i] = temp
        cnt[temp] = i
    return np.append(np.append(A,start),end)


def main():
    N,X,M = map(int,input().split())

    A = [-1 for i in range(M+2)]
    A[0] = X
    A = np.array(A)

    start = -1
    end = -1

    cnt = [0 for i in range(M)]
    cnt[X] = 0
    cnt = np.array(cnt)

    C = SerchLoop(M,A,cnt,start,end,0)
    A = C[:-2]
    start = C[-2]
    end = C[-1]

    L = end - start + 1

    if start == -1:
        straight = [0 for i in range(N)]
        for i in range(N):
            straight[i] = straight[i-1] + A[i]
        res = straight[-1]
    elif start == 0:
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        res = (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]
    else:
        straight = [0 for i in range(start)]
        for i in range(start):
            straight[i] = straight[i-1] + A[i]
        loop = [0 for i in range(L)]
        for i in range(L):
            loop[i] = loop[i-1] + A[start+i]
        if N >= start:
            res = straight[-1]
            N -= start
        else:
            res = straight[N-1]
            N = 0
        res += (N // L) * loop[-1]
        if N % L != 0:
            res += loop[N % L - 1]

    print(res)



main()
X = int(input())
if X = 3 or 5 or 7:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

X = int(input())
if X == 3 or X == 5 or X == 7:
  print('YES')
else:
  print('NO')
h,w=map(int,input().split())
grid=[None]*h

for i in range(h):
  grid[i]=input()

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  s=grid[i]
  left=0
  right=0
  while left<len(s):
    if s[left]=="#":
      left+=1
      right=left
      continue
    while s[right+1]=="." and right+1<len(s):
      right+=1
  
    for j in range(left,right+1):
      yoko[i][j]=right-left
      
    left=right+1
    right=left
    
for i in range(w):
  up=0
  down=0
  while up<h:
    if grid[down][i]=="#":
      up+=1
      down=up
      continue
    while grid[down+1][i]=="." and down+1<h:
      down+=1
    for j in range(up,down+1):
      tate[j][i]=down-right
    up=down+1
    down=up
    
ans=0
for i in range(h):
  for j in range(w):
    if grid[i][j]==".":
      ans=max(ans,tate[i][j]+yoko[i][j])
      
print(ans)

### FIXED CODE ###

h,w=map(int,input().split())
grid=[None]*h

for i in range(h):
  grid[i]=input()

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

for i in range(h):
  s=grid[i]
  left=0
  right=0
  while left<len(s):
    if s[left]=="#":
      left+=1
      right=left
      continue
    while right+1<w and s[right+1]==".":
      right+=1
  
    for j in range(left,right+1):
      yoko[i][j]=right-left
      
    left=right+1
    right=left
    
for i in range(w):
  up=0
  down=0
  while up<h:
    if grid[down][i]=="#":
      up+=1
      down=up
      continue
    while down+1<h and grid[down+1][i]==".":
      down+=1
    for j in range(up,down+1):
      tate[j][i]=down-up
    up=down+1
    down=up
    
ans=0
for i in range(h):
  for j in range(w):
    if grid[i][j]==".":
      ans=max(ans,tate[i][j]+yoko[i][j])
      
print(ans+1)
l = input().split(" ")
j = input().split(" ")
k = int(m[0])
n = int(m[1])
A = []
for i in range(j):
  d1 = j[i+1] - j[i]
  d2 = j[i+2] - j[i+1]
  min = min(d1,d2)
  A.append(int(min))
print(A)

### FIXED CODE ###

KN = input().split(' ')
K = int(KN[0])
N = int(KN[1])
M = K/2
Al = input().split(' ')
A = []

for home in Al:
  A.append(int(home))

m = A[0]+(K-A[-1])
 
for i in range(N-1):
  m = max(m,abs(A[i]-A[i+1]))

print(K-m)
s = input()
cnt = 0

for i in range(len(s)):
  if a[i] == '1':
    cnt+=1
    
 print(cnt)

### FIXED CODE ###

N = input()
ans = 0

if N[0] == '1':
    ans += 1
if N[1] == '1':
    ans += 1
if N[2] == '1':
    ans += 1
print(ans)
A = int(input(A))
B = int(input(B))
T = int(input(T))

count = (T + 0.5) // A
biscuit = B * count
print(biscuit)


### FIXED CODE ###

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

count = T // A
bsc = B * count

print(bsc)
X, Y = map(int, input().split())

if (X*2 - Y)%3 != 0 or (Y*2 - X)%3 != 0:
    print(0)
    exit()
else:
    X, Y = (X*2 - Y)//3, (Y*2 - X)//3
    p = [[0 for i in range(Y+2)]for j in range(X+2)]
    waru = 1000000007

    p[0][0]=1
    for y in range(Y+1):
        for x in range(X+1):
            p[x+1][y] += p[x][y] % waru
            p[x][y+1] += p[x][y] % waru

    print(p[X][Y]%waru)

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def combinations_mod(n, r, mod=1000000007):
    """Returns nCr in mod."""
    r = min(r, n - r)
    combs = 1
    for i, j in zip(range(n - r + 1, n + 1), range(1, r + 1)):
        combs *= (i % mod) * pow(j, mod - 2, mod)
        combs %= mod
    return combs


def main():
    X, Y = NMI()
    if (2*Y - X)%3 or (2*X - Y)%3:
        print(0)
        exit()

    A = (2*Y - X) // 3
    B = (2*X - Y) // 3
    if A < 0 or B < 0:
        print(0)
        exit()
    print(combinations_mod(A+B, A))


if __name__ == "__main__":
    main()
import sys
import string

alphabets=list(string.ascii_lowercase)

s=input()

l=len(s)

hm = lambda a,string: sum([x==a for x in string])

for x in range(l-1):
  if s[x]==s[x+1]:
    print('{} {}'.format(x+1, x+2))
    sys.exit()


for n in range(l-m):
  for a in alphabets:
    if hm(a,s[n:n+3])> m//2:
      print('{} {}'.format(n+1,n+m))
      sys.exit()
print('-1 -1')

### FIXED CODE ###

import sys
import string
 
alphabets=list(string.ascii_lowercase)
 
s=input()
 
l=len(s)
 
hm = lambda a,string: sum([x==a for x in string])
 
for x in range(l-1):
  if s[x]==s[x+1]:
    print('{} {}'.format(x+1, x+2))
    sys.exit()
 
 
for n in range(l-3):
  for a in alphabets:
    if hm(a,s[n:n+3])> 1:
      print('{} {}'.format(n+1,n+3))
      sys.exit()
print('-1 -1')
n = int(input())
h = list(map(int, input().split()))
if n==1:
    print('Yes')
    exit()
for i in range(n-1):
    if h[n-i] = h[n-i-1]-1:
        h[n-i-1] -= 1
    elif h[n-i] < h[n-i-1]-1:
        print('No')
        exit()
print('Yes')

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
if n==1:
    print('Yes')
    exit()
ht = h[-1]
for i in reversed(range(n-1)):
    if ht == h[i]-1:
        h[i]-=1
    elif ht < h[i]-1:
        print('No')
        exit()
    ht = h[i]
print('Yes')
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
suf = 0
for i in range (n):
  men1 = a[i]
  men2 = a[i + 1] 
  suf += b[men1]
  if (i != n - 1 )and(men1 + 1 == men2):
    suf += c[men1]
print(suf)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
suf = 0
for i in range (n):
  suf += b[i]
  if i >= 1 and a[i - 1]  + 1 == a[i]:
    suf += c[a[i - 1] - 1]
print(suf)
def main():
    from functools import lru_cache
    import sys
    readline = sys.stdin.readline

    @lru_cache(maxsize=None)
    def dfs(v, par=-1):
        """最長有向パスに含まれる頂点数"""
        ret = 0
        for u in g[v]:
            if u == par: continue
            ret = max(ret, dfs(u, v))
        return ret + 1

    n, m = map(int, readline().split())

    g = tuple(set() for _ in range(n))
    for _ in range(m):
        x, y = (int(c) - 1 for c in input().split())
        g[x].add(y)

    ret = 0
    for i in range(n):
        ret = max(ret, dfs(i))
    print(ret - 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)


def rec(v):
    if dp[v] != -1:
        return dp[v]

    res = 0
    for nv in g[v]:
        res = max(res, rec(nv) + 1)
    dp[v] = res
    return res


N, M = map(int, input().split())
g = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    g[x].append(y)

dp = [-1 for _ in range(N)]

ans = 0
for t in range(N):
    ans = max(ans, rec(t))
print(ans)
a, b, c = map(int, input().split())
 if a < b < c:
   print('Yes')
 else:
   print('No')
 

### FIXED CODE ###

a, b, c = map(int, input().split())
if a < b < c:
  print("Yes")
else:
  print("No")
a,b = map(int,input().split())
if a*b%2==0:
    print(Even)
elif a*b%2==1:
    print(Odd)
end





### FIXED CODE ###

a,b = map(int,input().split())
if a*b%2==0:
    print('Even')
elif a*b%2==1:
    print('Odd')
a,b,x = map(int,input().split())
Rb = range(0,b+1,x)
Mb = max(Rb)//x
Ra = range(0,a,x)
Ma = max(Ra)//x

print(Mb - Ma)

### FIXED CODE ###

a,b,x = map(int,input().split())
if a % x == 0:
    print(b//x - a//x + 1)
else:
    print(b//x - a//x)
scores = []
while True:
    n = int(input())
    if n == 0:
        break
    l = list(map(int, input().split()))
    scores.append(l)

for score in scores:
    print(pstdev(score))

### FIXED CODE ###

from statistics import pstdev

scores = []
while True:
    n = int(input())
    if n == 0:
        break
    l = list(map(int, input().split()))
    scores.append(l)

for score in scores:
    print(pstdev(score))
n = int(input())
n -= 1

alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']

first = n // len(alphabet)
mod = n % len(alphabet) 

if n < 26:
    print(alphabet[mod])
    
    
elif n >= 26 and n <702:
    print(alphabet[first-1]+alphabet[mod])
    
elif n >= 702 and n <18278:
    second = (first // len(alphabet)) -1
    second_1 = second % len(alphabet)
    print(alphabet[second_1-1]+alphabet[second-1]+alphabet[mod])
    
elif n >= 18278 and n <475254:
    second = (first // len(alphabet)) -1
    second_1 = second % len(alphabet)
    
    third = (second // len(alphabet)) -1 
    third_1 = third % len(alphabet)
    print(alphabet[second_1-1]+alphabet[second-1]+alphabet[mod]+alphabet[mod])
    
elif n >= 475254 and n <1000000000000001:
    print('')

### FIXED CODE ###

a = input()

if a.isupper() == True:
  print('A')
elif a.islower() == True:
  print('a')
a,b = map(int,input().split())
ptint(max(a+a-1,a+b,b+b-1))

### FIXED CODE ###

a,b = map(int,input().split())
print(max(a+a-1,a+b,b+b-1))
def dfs(x, y):
    C[y][x] = 0
    for dx,dy in zip([1,1,0,-1,-1,-1,0,1],[0,1,1,1,0,-1,-1,-1]):
        if 0 <= x+dx < w and 0 <= y+dy < h and C[y+dy][x+dx] == 1:
            dfs(x+dx, y+dy)

while 1:
    w,h = map(int,raw_input().split())
    if w == h == 0: break
    C = [map(int,raw_input().split()) for _ in xrange(h)]

    ans = 0
    for y in range(h):
        for x in range(w):
            if C[y][x] == 1:
                dfs(x, y)
                ans += 1
    print ans

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def dfs(x, y):
    C[y][x] = 0
    for dx,dy in zip([1,1,0,-1,-1,-1,0,1],[0,1,1,1,0,-1,-1,-1]):
        if 0 <= x+dx < w and 0 <= y+dy < h and C[y+dy][x+dx] == 1:
            dfs(x+dx, y+dy)

while 1:
    w,h = map(int,raw_input().split())
    if w == h == 0: break
    C = [map(int,raw_input().split()) for _ in xrange(h)]

    ans = 0
    for y in range(h):
        for x in range(w):
            if C[y][x] == 1:
                dfs(x, y)
                ans += 1
    print ans
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 4)
for i in range(m):
    a[int(input())] += 1

# 初期値
s0 = 1
if (a[1] == 1):
    s1 = 0
else:
    s1 = 1


def calc(l, acc1, acc2):
    # print("calc(l, acc1, acc2):" + str(l) + str(acc1) + str(acc2))
    if (l == 1):
        return acc2
    else:
        oldacc2 = acc2
        if (a[n - l + 2] == 1):
            acc2 = 0
        else:
            acc2 = (acc1 + acc2) % D
        acc1 = oldacc2
        return calc(l - 1, acc1, acc2)


print(calc(n, s0, s1))


### FIXED CODE ###

#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
D = 1000000007
n, m = map(int, input().split())
a = [0] * (10**5 + 1)
for i in range(m):
    a[int(input())] += 1

# 初期値
s = [0] * (n + 1)
s[0] = 1
if (a[1] == 1):
    s[1] = 0
else:
    s[1] = 1

# 暫定結果を格納する配列


def calc(n):
    if(a[n] == 1):
        return 0
    else:
        return (s[n - 1] + s[n - 2]) % D


def solver(n):
    for i in range(2, n + 1):
        s[i] = calc(i)


solver(n)
print(s[n])
def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if s in A:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1])
    print(answer[N] % 1000000007)

N, M = [int(x) for x in input().split()]
A = set()
for i in range(M):
    A.add(int(input().split()))
solve(N, M, A)



### FIXED CODE ###

def solve(N, M, A):
    answer = [0] * (N+1)
    answer[0] = 1
    if 1 in A:
        answer[1] = 0
    else:
        answer[1] = 1

    for s in range(2, N+1):
        if s in A:
            answer[s] = 0
        else:
            answer[s] = (answer[s-2] + answer[s-1]) % 1000000007
    print(answer[N])

N, M = [int(x) for x in input().split()]
A = set()
for i in range(M):
    A.add(int(input()))
solve(N, M, A)
S = input().split()
S_rev = list(reversed(S))
N = len(S)

if S != S_rev:
  print('No')
else:
  S1 = S[:(N-3)/2]
  S2 = S[(N-3)/2:]
  S1_rev = list(reversed(S1_rev))
  S2_rev = list(reversed(S2_rev))
  
  if S1==S1_rev and S2 == S2_rev:
    print('Yes')
  else:
    print('No')
  


### FIXED CODE ###

S = list(input())
S_rev = list(reversed(S))
N = len(S)
if S != S_rev:
  print('No')
else:
  S1 = S[:int((N-1)/2)]
  S2 = S[int((N+1)/2):]
  S1_rev = list(reversed(S1))
  S2_rev = list(reversed(S2))
  if S1==S1_rev and S2 == S2_rev:
    print('Yes')
  else:
    print('No')
I = input()
I = I.split(" ")
N = I[0]
K = I[1]
Q = I[2]

A = [0]*Q

for i in range(Q):
	A[i] = int(input())

point = [0]*N

for i in range(Q):
	point[A[i]-1] = point[A[i]-1] + 1

for i in range(Q):
	if point[i] > 0:
		print("yes")
	else:
		print("no")

### FIXED CODE ###

I = input()
I = I.split(" ")
N = int(I[0])
K = int(I[1])
Q = int(I[2])

A = [0] * Q

for i in range(Q):
	A[i] = int(input())

point = [0] * N

for i in range(Q):
	point[A[i]-1] = point[A[i]-1] + 1

for i in range(N):
	if Q - point[i] < K:
		print("Yes")
	else:
		print("No")
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

for i in range(K):
    if N-K+<i:
        print(0)
    else:
        print(comb(K-1,i)*comb(N-K+1,i+1)%div)

### FIXED CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

for i in range(K):
    if N-K<i:
        print(0)
    else:
        print(comb(K-1,i)*comb(N-K+1,i+1)%div)
n = int(input())
s = input()
a = {}
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      a.append(s[i] + s[j] + s[k])
print(len(s))

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(10):
  idx1=s.find(str(i))
  for j in range(10):
    idx2=s.find(str(j),idx1+1,n)
    for k in range(10):
      idx3=s.find(str(k),idx2+1,n)
      if idx1==-1 or idx2==-1 or idx3==-1:
        continue
      else:
        ans+=1
print(ans)
a=sorted(input())
for i in range(4)
	if a.count(a[0]) <= 3:
    print('Yes')
    break
print('No')

### FIXED CODE ###

s=input()
for i in range(2):
  count=1
  for j in range(i+1,4):
    if s[i] == s[j]:
      count+=1
    else:count=0
    if count >= 3:
      print('Yes')
      exit()
print('No')
class Node:
    def __init__(self, index):
        self.index = index
        self.leaf = set()
        self.score = 0

    def set_parent(self, parent):
        self.leaf.remove(parent)
        for l in self.leaf:
            tree[l].set_parent(self.index)

    def add_score(self, score):
        self.score += score
        for l in self.leaf:
            tree[l].add_score(score)


N, Q = map(int, input().split())
print(N, Q)
# tree = {i: Node(i) for i in range(1, N + 1)}
tree = {}
for i in range(1, N+1):
    tree[i] = Node(i)
print(len(tree))
tree[1].leaf.add(1)
for i in range(N-1):
    n1, n2 = map(int, input().split())
    tree[n1].leaf.add(n2)
    tree[n2].leaf.add(n1)

tree[1].set_parent(1)

for _ in range(Q):
    p, x = map(int, input().split())
    tree[p].add_score(x)

print(' '.join([str(t.score) for t in tree.values()]))


### FIXED CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
d = defaultdict(list)

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

c = defaultdict(int)

for _ in range(Q):
    p, x = map(int, input().split())
    c[p] += x

ans = [0 for i in range(N)]
que = [(1, 0, -1)]
while len(que) > 0:
    tmp = []
    for v, x, par in que:
        x += c[v]
        ans[v - 1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w, x, v))
    que = tmp

print(*ans)
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
ans = [0 for _ in range(n)]
D = dict()
S = set(A)
X = sorted(S, reverse=True)
for i, x in enumerate(X):
    D[x] = i

index = [n + 1 for _ in range(len(S))]
for i, a in enumerate(A):
    index[D[a]] = min(index[D[a]], i)

cnt = 0
x = n + 1

for i in range(1, len(S)):
    tmp = X[i - 1]
    nxt = X[i]
    cnt += C[tmp]
    x = min(x, index[D[tmp]])
    ans[x] += (tmp - nxt) * cnt

for i, a in enumerate(A):
    if a != 0:
        cnt += C[nxt]
        ans[i] += nxt * cnt
        break

for a in ans:
    print(a)


### FIXED CODE ###

from sys import exit
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
ans = [0 for _ in range(n)]
D = dict()
S = set(A)
if len(S) == 1:
    print(sum(A))
    for _ in range(n - 1):
        print(0)
    exit()
X = sorted(S, reverse=True)
for i, x in enumerate(X):
    D[x] = i

index = [n + 1 for _ in range(len(S))]
for i, a in enumerate(A):
    index[D[a]] = min(index[D[a]], i)

cnt = 0
x = n + 1

for i in range(1, len(S)):
    tmp = X[i - 1]
    nxt = X[i]
    cnt += C[tmp]
    x = min(x, index[D[tmp]])
    ans[x] += (tmp - nxt) * cnt

for i, a in enumerate(A):
    if a != 0:
        cnt += C[nxt]
        ans[i] += nxt * cnt
        break

for a in ans:
    print(a)
a = int(input())
x = list(map(int,input().split()))
ax = list(set(x))
x.sort()
ax = list(set(x))
def Y(a,t = 0):
    if a==t : print('YES')
    else : print('NO')
def y(a, t =0):
    if a==t : print('Yes')
    else : print('No')
if len(ax) < 3:
    if (sum(x) == 0) :
        print("Yes")
        exit()
    if x.count(0)*2 == x.count(ax[1]) and len(x) == x.count(0) + x.count(ax[1]):
        print("Yes")
        exit()
        
    print("No")
    exit()
t = (len(x) == x.count(ax[0]) + x.count(ax[1]) + x.count(ax[2])) * (x.count(ax[1]) == x.count(ax[0]) and x.count(ax[0]) == x.count(ax[2]))

y(1,t)

### FIXED CODE ###

a = int(input())
x = list(map(int,input().split()))
ax = list(set(x))
x.sort()
ax = list(set(x))
def ch(l):
    # print(l,l[1:] + [l[0]], l[2:] + [l[0]] +[l [1]])
    for i, j ,k in zip(l,l[1:] + [l[0]], l[2:] + [l[0]] +[l [1]]):
        if j != i ^ k: break
    else:
        return(1)
    return(0)
def Y(a,t = 0):
    if a==t : print('YES')
    else : print('NO')
def y(a, t =0):
    if a==t : print('Yes')
    else : print('No')
if len(ax) < 3:
    if (sum(x) == 0) :
        print("Yes")
        exit()
    if (len(ax)) <2:
        print("No")
        exit()
    if x.count(0)*2 == x.count(ax[1]) and len(x) == x.count(0) + x.count(ax[1]):
        print("Yes")
        exit()
        
    print("No")
    exit()
t = (len(x) == x.count(ax[0]) + x.count(ax[1]) + x.count(ax[2])) * (x.count(ax[1]) == x.count(ax[0]) and x.count(ax[0]) == x.count(ax[2]))*ch(ax)

y(1,t)
X = int(input())

def is_Prime(x):
  for i in range(2, x+1):
    if i * i + 1 > x:
      return True
    if x % i == 0:
      return False

for i in range(X+1, 2X+1):
  if is_Prime(i):
    print(i)
    break

### FIXED CODE ###

X = int(input())

def is_Prime(x):
  for i in range(2, x+1):
    if i * i + 1 > x:
      return True
    if x % i == 0:
      return False

for i in range(X, 2*X+1):
  if is_Prime(i):
    print(i)
    break
def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x.append(i)
        if i<0:y.append(i)
    x.sort(reverse=1)
    y.sort()
    if len(x)+len(y)<k or len(x)<k and (k-len(x))%2 and len(x)+len(y)<n:
        1/0
        print(0)
        exit()
    if len(x)<k and (k-len(x))%2:
        c=1
        for i in x+y[::-1][:k-len(x)]:
            c=c*i%M
        print(c)
        exit()
    x=x[:k]
    m=len(y)
    i=len(x)
    j=0
    if i<k:
        j=k-i
        x+=y[:j]
        j+=1
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()

### FIXED CODE ###

def main():
    M=10**9+7
    n,k,*a=map(int,open(0).read().split())
    x,y=[],[]
    for i in a:
        if i>0:x+=i,
        if i<0:y+=i,
    if len(x)+len(y)<k or k%2 and not x and len(y)<n:
        print(0)
        return
    if n==k or k%2 and not x:
        c=1
        for i in sorted(x+y)[-k:]:
            c=c*i%M
        print(c)
        return
    x=sorted(x)[::-1][:k]
    i=len(x)
    y.sort()
    m=len(y)
    j=k-i
    if j%2:
        x=x[:-1]
        i-=1
        j+=1
    x+=y[:j]
    while i>1 and j+1<m and x[i-1]*x[i-2]<y[j]*y[j+1]:
        x[i-1],x[i-2]=y[j],y[j+1]
        i-=2
        j+=2
    c=1
    for i in x:
        c=c*i%M
    print(c)
main()