Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

n, m, k = input().strip().split()
n, m, k = int(n), int(m), int(k)
friends = [0] + [[] for _ in range(n)]
blocks = [0] + [[] for _ in range(n)]

for _ in range(m):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    friends[p1].append(p2)
    friends[p2].append(p1)
for _ in range(k):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    blocks[p1].append(p2)
    blocks[p2].append(p1)

connected_num = 0
def dfs(graph, current, seen, connected_id):
    global connected_num
    seen[current] = connected_id
    connected_num += 1

    children = graph[current]
    for c in children:
        if seen[c] != -1:
            continue
        dfs(graph, c, seen, connected_id)

seen = [-1] * (n + 1)
connected_id = 0
connected = []
for i in range(1, n + 1):
    if seen[i] != -1:
        continue
    dfs(friends, i, seen, connected_id)
    connected.append(connected_num)
    connected_num = 0
    connected_id += 1

ans = []
for i in range(1, n + 1):
    i_connected_id = seen[i]
    exclude = 0
    for f in friends[i]:
        f_connected_id = seen[f]
        if i_connected_id == f_connected_id:
            exclude += 1
    for b in blocks[i]:
        b_connected_id = seen[b]
        if i_connected_id == b_connected_id:
            exclude += 1
    ans.append(str(connected[i_connected_id] - exclude - 1))

print(' '.join(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, m, k = input().strip().split()
n, m, k = int(n), int(m), int(k)
friends = [0] + [[] for _ in range(n)]
blocks = [0] + [[] for _ in range(n)]

for _ in range(m):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    friends[p1].append(p2)
    friends[p2].append(p1)
for _ in range(k):
    p1, p2 = input().strip().split()
    p1, p2 = int(p1), int(p2)
    blocks[p1].append(p2)
    blocks[p2].append(p1)

connected_num = 0
def dfs(graph, current, seen, connected_id):
    global connected_num
    seen[current] = connected_id
    connected_num += 1

    children = graph[current]
    for c in children:
        if seen[c] != -1:
            continue
        dfs(graph, c, seen, connected_id)

seen = [-1] * (n + 1)
connected_id = 0
connected = []
for i in range(1, n + 1):
    if seen[i] != -1:
        continue
    dfs(friends, i, seen, connected_id)
    connected.append(connected_num)
    connected_num = 0
    connected_id += 1

ans = []
for i in range(1, n + 1):
    i_connected_id = seen[i]
    exclude = 0
    for f in friends[i]:
        f_connected_id = seen[f]
        if i_connected_id == f_connected_id:
            exclude += 1
    for b in blocks[i]:
        b_connected_id = seen[b]
        if i_connected_id == b_connected_id:
            exclude += 1
    ans.append(str(connected[i_connected_id] - exclude - 1))

print(' '.join(ans))
import numpy as np
def resolve():
    K, Q = map(int, input().split())
    D = np.array(input().split(), dtype=np.int64)


    for _ in range(Q):
        n, x, m = map(int, input().split())
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = D % m
        acc_E = np.cumsum(E)

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero = [int(e == 0) for e in E]
        zero_acc = np.cumsum(zero)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    
import numpy as np
def resolve():
    K, Q = map(int, input().split())
    D = np.array(input().split(), dtype=np.int64)


    for _ in range(Q):
        n, x, m = map(int, input().split())
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = D % m
        acc_E = np.cumsum(E)

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero = [int(e == 0) for e in E]
        zero_acc = np.cumsum(zero)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###


import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

import numpy as np
def resolve():
    K, Q = map(int, inp().split())
    D = np.array(inp().split(), dtype=np.int64)
    nxm = [list(map(int, inp().split())) for _ in range(Q)]

    for n, x, m in nxm:
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = D % m
        acc_E = np.cumsum(E)

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero_acc = np.cumsum(E == 0).astype(np.int64)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    resolve()
import sympy

X=int(input())
flg=False
for A in range(-118,119):
    for B in range(-118,119):
        if A**5-B**5==X:
            print(str(A)+" "+str(B))
            flg=True
            break
    if flg:
        break


### FIXED CODE ###

X=int(input())
flg=False
for A in range(-120,120):
    for B in range(-120,120):
        if A**5-B**5==X:
            print(str(A)+" "+str(B))
            flg=True
            break
    if flg:
        break
n, k = map(int,input().split())
print(len([*filter(lambda hi: hi >= k, map(int,input().split()))]))

### FIXED CODE ###

n, k = map(int,input().split())
print(len(list(filter(lambda hi: hi >= k, map(int,input().split())))))
n,m=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
u=UnionFind(n)
for i in range(m):
  a,b,c=map(in,input().split())
  uf.merge(a-1,b-1)
print(len(u.parent))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
n,m=map(int,input().split())
class UnionFind(object):
    def __init__(self, N):
        self.parent = [i for i in range(N)]
 
    def merge(self, a, b):
        pa = self.root(a)
        pb = self.root(b)
        self.parent[pa] = pb
    
    def root(self, x):
        p = self.parent[x]
        if p == x:
            return x
        else:
            r = self.root(p)
            self.parent[x] = r
            return r
u=UnionFind(n)
for i in range(m):
  a,b,c=map(int,input().split())
  if a>b:
    a=g
    g=b
    b=a
  u.merge(a-1,b-1)
a=[0]*n
for i in range(n):
  a[i]=u.root(i)
print(len(set(a)))
def fun(li):
  for i in li:
    if i%2 == 0:
      if i%3 == 0 or i%5 ==0:
        continue;
      else:
        return "DENIED"
	return "APPROVED"      
n = int(input())
li = [int(num) for num in input().split(" ")]
print(fun(li))


### FIXED CODE ###

def fun(li):
  for i in li:
    if i%2 == 0:
      if i%3 == 0 or i%5 ==0:
        continue;
      else:
        return "DENIED"
  return "APPROVED"
n = int(input())
li = [int(num) for num in input().split(" ")]
print(fun(li))
r,d,x=map(int,input().split())
for i range(10):
  x=r*x-d
  print(x)

### FIXED CODE ###

r,d,x=map(int,input().split())
for i in range(10):
  x=r*x-d
  print(x)
import sys
import numpy as np

from collections import deque 
from functools import reduce

# input = sys.stdin.readline

x, y, a, b, c = map(int, input().split())

p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

list.sort(p, reverse=True)
list.sort(q, reverse=True)
list.sort(r, reverse=True)

p_np = np.zeros(999999)
q_np = np.zeros(999999)

if len(p) > x:
    p_np[:x] = p[:x]
else:
    p_np[:len(p)] = p[:]

if len(q) > y:
    q_np[:y] = q[:y]
else:
    q_np[:len(q)] = q[:]    

ap_np = np.hstack((p_np[:x], q_np[:y]))
ap_np.sort()
ap_cnt = 0

for i, ri in enumerate(r):
    if (r[i] > ap_np[i]):
        ap_np[i] = r[i]
        break
print(int(ap_np.sum()))

### FIXED CODE ###

import sys
import numpy as np

from collections import deque 
from functools import reduce

# input = sys.stdin.readline

x, y, a, b, c = map(int, input().split())

p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

list.sort(p, reverse=True)
list.sort(q, reverse=True)
list.sort(r, reverse=True)

p_np = np.zeros(999999)
q_np = np.zeros(999999)

if len(p) > x:
    p_np[:x] = p[:x]
else:
    l_p = len(p)
    p_np[:l_p] = p[:]

if len(q) > y:
    q_np[:y] = q[:y]
else:
    l_q = len(q)
    q_np[:l_q] = q[:]
ap_np = np.hstack((p_np[:x], q_np[:y]))
ap_np.sort()
ap_cnt = 0

for i, ri in enumerate(r):
    if i >= x + y:
        break
    if (r[i] > ap_np[i]):
        ap_np[i] = r[i]
print(int(ap_np.sum()))
n = int(input())
S=[]
for i in range(n):
  S.append(int(input()))
T = set(S)
print(len(T))

### FIXED CODE ###

n = int(input())
S=[]
for i in range(n):
  S.append(input())
T = set(S)
print(len(T))
n=input()
l=[int(input()) for i in range(n)]
s=set(l)
print(len(s))


### FIXED CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
s=set(l)
print(len(s))
print('YES' if int(input()) in [3,5,7] else 'NO']

### FIXED CODE ###

x=int(input())
print('YES' if x in [3,5,7] else 'NO')
# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))
# 例外の処理をもうちょい詰める
limit = [1]
for i in range(1, N+1):

    if i == N:
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()
    # if A[0] == 0:
    #     print(3-A[-1])
    #     exit()
    # else:
    #     print(-1)
    #     exit()

# 最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
ans.reverse()

for i in range(N):
    if (ans[i]-A[i])*2 >= A[i+1]:
        continue
    else:
        print(-1)
        exit()

print(sum(ans))


### FIXED CODE ###

# 深さdの上限を先に決める
N = int(input())
# Aは，葉として残す必要があるものの数
A = list(map(int, input().split()))

# 深さdのノード数の上限
limit = [1]
for i in range(1, N+1):
    if i == N:  # 一番深いところの上限はA[N]
        limit.append(A[i])
    else:
        limit.append((limit[-1]-A[i-1])*2)
        if limit[-1] < 0:
            print(-1)
            exit()

# Nが0の時の処理
if N == 0:
    if A[0] != 1:
        print(-1)
        exit()

# 一番深いところから構築して最後にsumをとる
ans = [A[-1]]
now_leaf = A[-1]  # 一番深いところから構築しており，今現在の葉の数
for i in range(N-1, -1, -1):
    # print(A[i])
    ans.append(min(now_leaf+A[i], limit[i]))
    now_leaf = ans[-1]
# 構築したものに対してジャッジする, 葉を確保できているかどうか
for i in range(N):
    # ans[N-i]とすることで，今は一番浅いところから見ている
    if (ans[N-i]-A[i])*2 < A[i+1]:  # 葉が確保できているか
        print(-1)
        exit()
print(sum(ans))
import numpy as np
a, b, n = map(int, input().split())
x = np.arange(1, b+1)
y = np.floor(a * x / b) - a * np.floor(x / b)
print(y)
print(int(y.max()))

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = min(b - 1, n)
print(math.floor(a * x / b) - a * math.floor(x / b))
def judge(A, B, C, M):
	result = C
	for i in range(M):
		result += A[i] * B[i]

	return result > 0

def main():
	N, M, C = map(int, input().split())
	B = map(int, input().split())
	count = 0

	for i in N:
		A = map(int, input().split())

		if judge(A, B, C, M):
			count += 1

	print(count)



if __name__ == '__main__':
	main()

### FIXED CODE ###

def judge(A, B, C, M):
	result = C
	for i in range(M):
		result += A[i] * B[i]

	return result > 0

def main():
	N, M, C = map(int, input().split())
	B = [int(x) for x in input().split()]
	count = 0

	for i in range(N):
		A = [int(x) for x in input().split()]

		if judge(A, B, C, M):
			count += 1

	print(count)



if __name__ == '__main__':
	main()
import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
  print(dp[n])
calc()

### FIXED CODE ###

import sys
input=sys.stdin.readline

def calc():
  mod=998244353
  n,s=map(int,input().split())
  arr=list(map(int,input().split()))
  dp=[0]*(s+1)
  dp[0]=1
  ans=0
  for i in range(1,n+1):
    val=arr[i-1]
    for k in range(s,-1,-1):
      dp[k]*=2
      dp[k]%=mod
      if k>=val and dp[k-val]!=0:
        dp[k]+=dp[k-val]
        dp[k]%=mod
  print(dp[s]%mod)
calc()
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

n, x = map(int, input().split())
city = list(map(int, input().split()))
city.append(x)
city = sorted(city)
diff = [city[i+1] - city[i] for i in range(len(city)-1)]

if len(diff)==1:
    print(diff[0])
else:
    print(gcd_list(diff))

### FIXED CODE ###

from functools import reduce
from fractions import gcd

def gcd_list(numbers):
    return reduce(gcd, numbers)

n, x = map(int, input().split())
city = list(map(int, input().split()))
city.append(x)
city = sorted(city)
diff = [city[i+1] - city[i] for i in range(len(city)-1)]

if len(diff)==1:
    print(diff[0])
else:
    print(gcd_list(diff))
def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par = get_par(par_list[x])
    par_list[x] = par
    return par

N,M=map(int,input().split())
par_list = [i for i in range(N)]
for i in range(M):
  Xi,Yi,Zi=map(int,input().split())
  par_Xi = get_par(Xi-1)
  par_Yi = get_par(Yi-1)
  if par_Xi != par_Yi:
    par_list[par_Yi] = par_list[par_Xi]
    
#print(par_list)
set_uf = set()
for par in par_list:
  set_uf.add(get_par(par))
  
print(len(set_uf))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

N,M=map(int,input().split())
par_list = list(range(N))
for i in range(M):
  Xi,Yi,Zi=map(int,input().split())
  par_Xi = get_par(Xi-1)
  par_Yi = get_par(Yi-1)
  if par_Xi != par_Yi:
    par_list[par_Yi] = par_Xi
    
set_uf = set()
for par in par_list:
  set_uf.add(get_par(par))
  
print(len(set_uf))
if __name__ == '__main__':
    S = input()
    T = input()
    print(T+S)

### FIXED CODE ###

str1 , str2 = input().split(" ")
str3 = str2+str1
print(str3)
X, Y = map(int, input().split())

ans = max(0, (4 - X) * 100000)
ans+ = max(0, (4 - Y) * 100000)

if X == Y == 1:
    ans += 100000 * 4

print (ans)

### FIXED CODE ###

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

ans = max(0, (4 - X) * 100000)
ans+= max(0, (4 - Y) * 100000)

if X == Y == 1:
    ans += 100000 * 4

print (ans)
def segfunc(x, y): return max(x, y)

def update(i, x):
    i += MAX_N - 1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2+1], node[i*2+2])

def query(l, r):
    L = l + MAX_N
    R = r + MAX_N
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(N-1).bit_length()
MAXINDEX = 2 ** (30000).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * MAXINDEX)
INF = 0
ma = max(a)
ans = 0
for i in a:
    tmp = query(max(i - K, 0), min(ma, i + K) + 1)
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)


### FIXED CODE ###

def segfunc(x, y): return max(x, y)

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

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

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))
n = input()
m = [ int(x) for x in input().split() ]

i = max(m)
j = min(m)

print( i - j )

### FIXED CODE ###

cs = [ int(x) for x in input().split() ]
n = cs[0] * 100 + cs[1] * 10 + cs[2]
if n % 4 == 0 :
            print("YES")
else :
            print("NO")
import sys
input = sys.stdin.readline

# D - Derangement
def swap(index, swap_with_right):
  global p

  if swap_with_right:
    l = index
    r = index + 1
  else:
    l = index - 1
    r = index

  pl = p[l]
  pr = p[r]
  p[l] = pr
  p[r] = pl


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

p.insert(0, 0)
ans = 0

if p[1] == 1:
  swap(1, True)
  ans += 1

for i in range(2, N+1):
	if i == p[i] and i+1 == p[i+1]:
		swap(i, True)
		ans += 1
	elif i == p[i]:
		ans += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# D - Derangement
def swap(index, swap_with_right):
  global p

  if swap_with_right:
    l = index
    r = index + 1
  else:
    l = index - 1
    r = index

  pl = p[l]
  pr = p[r]
  p[l] = pr
  p[r] = pl


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

p.insert(0, 0)
ans = 0

if p[1] == 1:
  swap(1, True)
  ans += 1

for i in range(2, N+1):
	if i < N:
		if i == p[i] and i+1 == p[i+1]:
			swap(i, True)
			ans += 1
		elif i == p[i]:
			ans += 1
	elif i == p[i]:
		ans += 1

print(ans)
x=raw_input()
print (x*x*x)

### FIXED CODE ###

x=int(raw_input())
print x*x*x
n,k= list(map(int, input().split()))
s = input()

abc = "ABCAB" * 10

abc = abc[:n+1]
print( abc[:k] + abc[k].lower() + abc[k+1:-1])


### FIXED CODE ###

n,k= list(map(int, input().split()))
s = input()
s = s[:n]
k -= 1


print(s[:k] + s[k].lower() + s[k+1:])
a,b=map(int,input().split())
x=a+b
y=a-b
z=a*b
if x>=y and x>=z:
    print(x)
if y>=x and y>=z:
    print(y):
if z>=x and z>=y:
     print(z)
    


### FIXED CODE ###

a,b=map(int,input().split())
x=a+b
y=a-b
z=a*b
print(max(x,y,z))
from sys import stdin

input = stdin.readline
MOD = 10 ** 9 + 7


def solve():
    N, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(key=abs, reverse=True)
    noneg = 1
    res = 1
    i = 0
    platest = -1
    nlatest = -1
    ind = set()
    while i < k:
        if a[i] > 0:
            ind.add(i)
            platest = i
        elif a[i] < 0:
            if noneg:
                noneg = 0
                nlatest = i
            else:
                noneg = 1
                ind |= {nlatest, i}
        i += 1
    if not noneg:
        pnext = -1
        nnext = -1
        while i < N and (pnext == -1 or nnext == -1):
            if a[i] > 0 and pnext == -1:
                pnext = i
            elif a[i] < 0 and nnext == -1:
                nnext = i
            i += 1
        t1 = float('-inf')
        t2 = float('-inf')
        if platest != -1 and nnext != -1:
            t1 = abs(a[nnext]) / a[platest]
        if pnext != -1:
            t2 = a[pnext] / abs(a[nlatest])
        else:
            if a[-1] == 0:
                print(0)
                return
            else:
                res = 1
                for i in range(N-1,N-k-1,-1):
                    res *= a[i]
                    res %= MOD
                print(res)
                return
        if t1 >= t2:
            ind.discard(platest)
            ind.add(a[nnext])
        else:
            ind.discard(nlatest)
            ind.add(a[pnext])
        res = 1
    for i in ind:
        res *= a[i]
        res %= MOD
    print(res)



if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

def main():
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    l, r = 0, N-1
    MOD = 10**9+7
    if K == N:
        ans = 1
        for num in A:
            ans *= num
            ans %= MOD
        print(ans)
        exit()
    elif A[-1] < 0 and K%2 == 1:
        ans = 1
        for i in range(K):
            ans *= A[-i-1]
            ans %= MOD
        print(ans)
        exit()
    ans = 1
    if K%2 == 1:
        ans *= A[-1]
        r -= 1
    for _ in range(K//2):
        nl = A[l]*A[l+1]
        nr = A[r]*A[r-1]
        if nl > nr:
            ans *= nl
            l += 2
        else:
            ans *= nr
            r -= 2
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()
sys.setrecursionlimit(10 ** 5 + 10)
mod = 10 ** 9 + 7

# フィボナッチ数列
fib_memo = {}
def fib(N):
    if N < 2: return 1
    if N not in fib_memo:
        fib_memo[N] = fib(N-1) + fib(N-2)
    return fib_memo[N]

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

tmp_list = [0] * (M+1)
now_kaidan = 0
for i in range(M):
    tmp_list[i] = (A[i] - 1) - now_kaidan
    now_kaidan = A[i] + 1
tmp_list[-1] = N-now_kaidan
ans = 1

for v in tmp_list:
    if v == -1:     # 壊れた階段が連続している時は0移動方法がない
        print(0)
        exit()
    ans *= fib(v)
    ans %= mod

print(ans%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
mod = 10 ** 9 + 7

# フィボナッチ数列
fib_memo = {}
def fib(N):
    if N < 2: return 1
    if N not in fib_memo:
        fib_memo[N] = fib(N-1) + fib(N-2)
    return fib_memo[N]

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

tmp_list = [0] * (M+1)
now_kaidan = 0
for i in range(M):
    tmp_list[i] = (A[i] - 1) - now_kaidan
    now_kaidan = A[i] + 1
tmp_list[-1] = N-now_kaidan
ans = 1

for v in tmp_list:
    if v == -1:     # 壊れた階段が連続している時は0移動方法がない
        print(0)
        exit()
    ans *= fib(v)
    ans %= mod

print(ans%mod)
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

a = np.array(a)

s = 0
e = 0

arr = []
for s in range(N):
    for e in range(s+1, N+1):
        arr.append(a[s:e])

max_len = len(bin(np.sum(a))[2:])

su = 0
b = [bin(np.sum(aa))[2:] for aa in arr]
b = ['0' * (max_len - len(bb)) + bb for bb in b]
while True:
    c = [bb for bb in b if bb[0] == '1']
    if len(c) >= K:
        su += 2 ** (len(c[0]) - 1)
        b = [cc[1:] for cc in c]
    else:
        b = [bb[1:] for bb in b]
    if len(b[0]) == 0:
        break
print(su)

### FIXED CODE ###

import numpy as np
N, K = list(map(int,input().split()))
a = list(map(int,input().split()))

a = np.array(a)

s = 0
e = 0

arr = []
aa = np.append(0,np.cumsum(a))
for s in range(len(aa)):
    for e in range(s+1, len(aa)):
        arr.append(aa[e] - aa[s])

max_len = len(bin(np.sum(a))[2:])

su = 0
b = [bin(aa)[2:] for aa in arr]
b = ['0' * (max_len - len(bb)) + bb for bb in b]
while True:
    c = [bb for bb in b if bb[0] == '1']
    if len(c) >= K:
        su += 2 ** (len(c[0]) - 1)
        b = [cc[1:] for cc in c]
    else:
        b = [bb[1:] for bb in b]
    if len(b[0]) == 0:
        break
print(su)