Harryxun/stf_run huggingface dataset:
from sys import stdin, setrecursionlimit
from collections import deque


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    p = []
    m = []

    for _ in range(n):
        a, b = map(int, input().split())
        f = b / a
        if f < 0:
            m.append(-1 / f)
        elif f > 0:
            p.append(f)

    g_p = {}
    for k in p:
        if k in g_p:
            g_p[k] += 1
        else:
            g_p[k] = 1
    g_m = {}
    for k in m:
        if k in g_m:
            g_m[k] += 1
        else:
            g_m[k] = 1

    ans = 1

    for k in g_p:
        if k in g_m:
            ans *= (2 ** g_p[k] + 2 ** g_m[k] - 1)
        else:
            ans *= 2 ** g_p[k]
        ans %= mod
    for k in g_m:
        if not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans - 1) % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit


def gcd(x, y):
    if x % y == 0:
        return y
    return gcd(y, x % y)


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    p = []
    m = []

    zz = 0

    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0 and b != 0:
            g = gcd(a, b)
            f = b / a
            if b / a < 0:
                m.append(str(abs(a // g)) + ':' + str(abs(b // g)))
            elif f > 0:
                p.append(str(abs((b // g))) + ':' + str(abs((a // g))))
        elif a == 0 and b == 0:
            zz += 1
        elif a == 0:
            m.append(0)
        elif b == 0:
            p.append(0)

    g_p = {}
    for k in p:
        if k in g_p:
            g_p[k] += 1
        else:
            g_p[k] = 1
    g_m = {}
    for k in m:
        if k in g_m:
            g_m[k] += 1
        else:
            g_m[k] = 1

    ans = 1

    for k in g_p:
        if k in g_m:
            ans *= (2 ** g_p[k] + 2 ** g_m[k] - 1)
        else:
            ans *= 2 ** g_p[k]
        ans %= mod
    for k in g_m:
        if not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans + zz - 1) % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()
N, M = map(int,input().split())

e = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    e[a] += 1
  elif(b == N):
    e[b] += 1
if(2 in e):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")

### FIXED CODE ###

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

tmp = [0]*N
check = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    tmp[b] += 1
  elif(b == N):
    check[a] += 1

for i in range(len(tmp)):
  if(check[i] == 1 and tmp[i] == 1):
    print("POSSIBLE")
    break
else:
  print("IMPOSSIBLE")

"""
tmp = [0]*N
for _ in range(M):
  a, b = map(int,input().split())
  if(a == 1):
    tmp[b] += 1
  elif(b == N):
    tmp[a] += 1

if(2 in tmp):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
"""
N,M=map(int,input().split())
mod=10**9+7
n1=0
n2=0
A=[]
for i in range(M):
  n1=n2
  n2=int(input())
  #print(n2-n1+1)
  A.append(n2-n1-2)
A.append(N-n2-1)
if A[0]==-1:
  A.pop(0)
else:
  A[0]=A[0]+1
#print(A)
mx=max(A)
dp=[0 for i in range(mx+1)]
dp[0]=1
dp[1]=1
for i in range(mx-1):
  dp[i+2]=(dp[i]+dp[i+1])%mod
dp[0]=0
dp.append(0)
#print(dp)
ans=1
for i in range(len(A)):
  ans=(ans*dp[A[i]])%mod
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
A=set(A)
#print(A)
for i in range(1,N+1):
  if dp[i-1]==0 and dp[i-2]==0:
    break
  elif i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)
a=input()
s=int(a)
if s<86400 and s>=0:

    h=int(s/3600)
    m=int((s-h*3600)/60)
    s=s-h*3600-m*60

    print(h,":",m,":",s)

else:
    exit()

### FIXED CODE ###

a,b=input().split()
if int(a)<1 or int(b)>100:
    exit()
else:
   c=int(a)*int(b)
   d=int(a)*2+int(b)*2

print(c,d)
from collections import Collection
import math

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

c = Collection(A)

all_ans = 0
for n in c.values():
    if n <= 1:
        continue
    all_ans += math.factorial(n)//(math.factorial(n-2)*math.factorial(2))

for n in A:
    print(all_ans - (c[n]-1))

### FIXED CODE ###

from collections import Counter
import math

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

c = Counter(A)

all_ans = 0
for n in c.values():
    if n <= 1:
        continue
    all_ans += math.factorial(n)//(math.factorial(n-2)*math.factorial(2))

for n in A:
    print(all_ans - (c[n]-1))
n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]
import numpy as np

ls = np.array([[i-j, i+j] for i, j in xl])
ls = ls[ls[:, 0].argsort()]
 
i, dr = 0, 0
while True:
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls = np.delete(ls, i+1, 0)
    else:
        i += 1
        if i+1 >= len(ls):
            break
print(len(ls))

### FIXED CODE ###

n = int(input())
xl = [[int(i) for i in input().split(' ')] for j in range(n)]

ls = sorted([[i-j, i+j] for i, j in xl], key=lambda x: x[1])

i, dr = 0, 0
while True:
    if (len(ls)<=1) | (i+1 >= len(ls)):
        break
    a, b = ls[i], ls[i+1]
    if a[1]>b[0]:
        dr += 1
        ls.pop(i+1)
    else:
        i += 1

print(len(ls))
a, b, k = map(int, input().split())

ans = 0

lista = range(a+1)
aa = lista.pop(0)

listb = range(b+1)
bb = listb.pop(0)

if (a < b):
    li = [i for i in listb if a % i == 0 && b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]
else:
    li = [i for i in lista if a % i == 0 && b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]

print(ans)

### FIXED CODE ###

a, b, k = map(int, input().split())

ans = 0

lista = list(range(a+1))
aa = lista.pop(0)

listb = list(range(b+1))
bb = listb.pop(0)

if (a < b):
    li = [i for i in lista if a % i == 0 and b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]
else:
    li = [i for i in listb if a % i == 0 and b % i == 0]
    li = sorted(li, reverse=True)
    ans = li[k-1]

print(ans)
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh_, dw_ = map(int, input().split())

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.append((ch-1,cw-1))
while len(q)>0:
    h,w = q.popleft()
    cnt = dps[h][w]
    # 先に魔法を使っておく
    for dh in range(-2,3):
        for dw in range(-2,3):
            hn = h + dh
            wn = w + dw
            if (dh,dw) in mvs:
                if 0<=hn<H and 0<=wn<W:
                    if dps[hn][wn] <= cnt:continue
                    if fs[hn][wn] == ".":
                        q.append((hn, wn))
                        dps[hn][wn] = min(dps[h][w], cnt)
            else:
                if 0<=hn<H and 0<wn<W:
                    if dps[hn][wn] <= cnt+1:continue
                    if fs[hn][wn] == ".":
                        q.appendleft((hn,wn))
                        dps[hn][wn] = min(dps[hn][wn], cnt + 1)

# for r in dps:
#     print(*r)
ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)


### FIXED CODE ###

H, W, m = map(int, input().split())
hs = [0] * (H+1)
ws = [0] * (W+1)
from collections import defaultdict
d = defaultdict(bool)
N = 10**6
for i in range(m):
    hi,wi = map(int, input().split())
    hi -= 1
    wi -= 1
    hs[hi] += 1
    ws[wi] += 1
    d[hi*10**6+wi] = True

hmx = max(hs)
hset = set()
for i,h in enumerate(hs):
    if h == hmx:
        hset.add(i)
wmx = max(ws)
wset = set()
for j, w in enumerate(ws):
    if w == wmx:
        wset.add(j)

flg = False
ans = 0
cnt = 0
for i in hset:
    for j in wset:
        ans = max(ans, hmx+wmx-d[i*N+j]) 
        if cnt >= m:
            flg = True
            break
        cnt += 1
    if flg:break

print(ans)
N, R = map(int, input().split())
print(R+100*(10-min(10,K)))

### FIXED CODE ###

N, R = map(int, input().split())
print(R+100*(10-min(10,N)))
import math
n = int(input())
A = list(map(int, input().split())).sort(reverse=True)

if len(A) <= 2:
    print(sum(A))
else:
    ans = A[0] + 2*sum(A[1:math.floor(n/2)]) + (N%2)*A[math.floor[N/2]]
    print(ans)


### FIXED CODE ###

import math
n = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

ans = A[0] + 2*sum(A[1:math.floor(n/2)]) + (n%2)*A[math.floor(n/2)]
print(ans)
import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 7)
     
    # 遅延評価で加えてあげるだけ
     
    N,Q = map(int,input().split())
    AB = [[int(x) for x in input().split()] for _ in range(N-1)]
    PX = [[int(x) for x in input().split()] for _ in range(Q)]
     
    graph = [[] for _ in range(N+1)]
    for a,b in AB:
        graph[a].append(b)
        graph[b].append(a)
     
    value = [0] * (N+1)
    for p,x in PX:
        value[p] += x
     
    def dfs(v,parent,add):
        value[v] += add
        for x in graph[v]:
            if x == parent:
                continue
            dfs(x,v,value[v])
     
    dfs(1,0,0)
     
    answer = ' '.join(map(str,value[1:]))
    print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
    
# 遅延評価で加えてあげるだけ
    
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
    
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
    
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
    
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
    
dfs(1,0,0)
    
answer = ' '.join(map(str,value[1:]))
print(answer)
a = input()
b = input()

if a == b:
  print ("H")
else:
  print ("D")

### FIXED CODE ###

a, b = map(str, input().split())

if a==b:
	print ("H")
else:
  	print("D")
n = int(input())
A = list(input().split())
for i in range(n):
    A[i] = int(A[i])
m = int(input())
B = list(input().split())
for i in range(m):
    B[i] = int(B[i])

def solve(x,y):
    if x==n:
        S[y] = 1
    else:
        solve(x+1,y)
        if y+A[x] < 2001:
            solve(x+1,y+A[x]
            
S = [0 for i in range(2001)]

solve(0,0)
    
for i in range(m):
    if S[B[i]] == 1:
        print("yes")
    else:
        print("no")




### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
m = int(input())
B = list(map(int,input().split()))

T = [[0]*2001 for i in range(n)]

T[0][0] = 1
T[0][A[0]] = 1
for i in range(1,n):
    for j in range(2001):
        T[i][j] = T[i-1][j]
        if (j - A[i] >=0) and (T[i-1][j-A[i]] == 1):
            T[i][j] = 1
    
for i in range(m):
    if T[n-1][B[i]] == 1: print("yes")
    else: print("no")
s = input()
 
if (s[-1]==2,4,5,7,9):
  print（"hon")
elif (s[-1]==0,1,6,8):
  print("pon")
else:
  print("bon")







### FIXED CODE ###

s = input()
if (s[-1]=="2" or s[-1]=="4" or s[-1]=="5" or s[-1]=="7" or s[-1]=="9"):
  print("hon")
elif (s[-1]=="0" or s[-1]=="1" or s[-1]=="6" or s[-1]=="8"):
  print("pon")
else:
  print("bon")
S = list(input())

ans = []
ans_ = 0
for s in S:
    if s=="A" or s=="C" or s=="G" or s=="T":
        ans_ += 1
    else:
        ans.append(ans_)
        ans_ = 0
print(max(ans))


### FIXED CODE ###

S = list(input())

ans = [0]
ans_ = 0
for s in S:
    if s == "A" or s == "C" or s == "G" or s == "T":
        ans_ += 1
    else:
        ans.append(ans_)
        ans_ = 0
ans.append(ans_)
print(max(ans))
a, b, c, d = map(int, input().split())

if ab(a-b) <= d and bc(b-c) <= d or ac(a-c) <= d:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

if abs(a-b) <= d and abs(b-c) <= d or abs(a-c) <= d:
    print('Yes')
else:
    print('No')
b = input()
l = len(b)
ans = []
kotae = 1
c = []
for i in range(l):
  if b[i]=="A" or b[i]=="T" or b[i]=="G" or b[i]=="C":
    ans.append(i)
l2 = len(ans)
for i in range(l2-1):
  if (ans[i+1]-ans[i])==1 and i==l2-2:
    kotae+=1
    c.append(kotae)
  elif (ans[i+1]-ans[i])==1:
    kotae+=1
  else:
    c.append(kotae)
    kotae=1
if ans==[]:
  print(0)
else:print(max(c))

### FIXED CODE ###

b = input()
l = len(b)
ans = []
kotae = 1
c = []
for i in range(l):
  if b[i]=="A" or b[i]=="T" or b[i]=="G" or b[i]=="C":
    ans.append(i)
l2 = len(ans)
if l2==1:
  c.append(1)
for i in range(l2-1):
  if (ans[i+1]-ans[i])==1 and i==l2-2:
    kotae+=1
    c.append(kotae)
  elif (ans[i+1]-ans[i])==1:
    kotae+=1
  else:
    c.append(kotae)
    kotae=1
if ans==[]:
  print(0)
else:print(max(c))
import math

r = int(input())

print(f' {math.pi * r ** 2}{math.pi * r * 2}')



### FIXED CODE ###

import math

r = float(input())

print(f' {math.pi * r ** 2} {math.pi * r * 2}')
a,b,c=sorted(map(int,input().split())
print(c-a)

### FIXED CODE ###

a,b,c=sorted(map(int,input().split()))
print(c-a)
length = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K = int(input())


print(length[K])


### FIXED CODE ###

length = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

K = int(input())


print(length[K-1])
y,m,d=str(input().split("/")
if y<=2018:
  ans="Heisei"
else:
  if m<=4:
    ans="Heisei"
  else:
    ans="TBD"
print(ans)


### FIXED CODE ###

y,m,d=map(int,input().split("/"))
if y<=2018:
  ans="Heisei"
else:
  if m<=4:
    ans="Heisei"
  else:
    ans="TBD"
print(ans)
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
num=[2,5,5,4,5,6,3,7,6]

#最小本数で作成可能な数字をリスト化
creat_A=[]
for n in A:
  creat_A.append(num[n-1])
mA=min(creat_A)

#dp[N]:N本のマッチ棒を使って作ることのできる最大桁数
dp=[-1 for _ in range(N+1)]
for i in range(M):
  if creat_A[i] <= N:
    dp[creat_A[i]]=1

for i in range(mA,N):
  for j in range(M):
    if i+creat_A[j] <= N and dp[i] > 0:
      dp[i+creat_A[j]]=max(dp[i+creat_A[j]],dp[i]+1)

#dp[N]から使用した数字の数を算出。
ans=[0 for _ in range(10)]

now=N
while dp[now] > 0:
  res=-1
  temp_i=-1
  for i in range(M):
    if dp[now-creat_A[i]]==dp[now]-1:
      if res < A[i]:
        res=A[i]
        temp_i=i
  if res==-1:
    break
  else:
    ans[res]+=1
    now-=creat_A[temp_i]
temp2=0
for i in range(M):
  if creat_A[i]==now:
    temp2=max(temp2,A[i])
ans[temp2]+=1

#答えの出力。最小から加えて逆向きに読めばOK
ansans=""
for i in range(10):
  if ans[i]>0:
    ansans+=(str(i)*ans[i])
ansans=ansans[::-1]
print(ansans)

### FIXED CODE ###

N,M=map(int,input().split())
A=[int(x) for x in input().split()]
num=[2,5,5,4,5,6,3,7,6]

#最小本数で作成可能な数字をリスト化
creat_A=[]
for n in A:
  creat_A.append(num[n-1])

#dp[N]:N本のマッチ棒を使って作ることのできる最大桁数
dp=[-1 for _ in range(N+1)]
for i in range(M):
  if creat_A[i] <= N:
    dp[creat_A[i]]=1

for i in range(N):
  if dp[i]>0:
    for j in range(M):
      if i+creat_A[j] <= N:
        dp[i+creat_A[j]]=max(dp[i+creat_A[j]],dp[i]+1)

#dp[N]から使用した数字の数を算出。
ans=[0 for _ in range(10)]

now=N
while dp[now] > 0:
  res=-1
  temp_i=-1
  for i in range(M):
    if now-creat_A[i] >0 and dp[now-creat_A[i]]==dp[now]-1:
      if res < A[i]:
        res=A[i]
        temp_i=i
  if res==-1:
    break
  else:
    ans[res]+=1
    now-=creat_A[temp_i]
    
temp2=0
for i in range(M):
  if creat_A[i]==now:
    temp2=max(temp2,A[i])
ans[temp2]+=1

#答えの出力。最小から加えて逆向きに読めばOK
ansans=""
for i in range(10):
  if ans[i]>0:
    ansans+=(str(i)*ans[i])
ansans=ansans[::-1]
print(ansans)
def examC():
    N = I()
    a = LI()
    lower = min(a)
    L = (max(a)-min(a))
    cur = [0]*L
    for i in range(L):
        for j in range(N):
            cur[i] +=(a[j]-(i+lower))**2
    ans = min(cur)
    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

### FIXED CODE ###

def examC():
    N = I()
    a = LI()
    lower = min(a)
    L = (max(a)-min(a))
    cur = [0]*L
    for i in range(L):
        for j in range(N):
            cur[i] +=(a[j]-(i+lower))**2
    if cur:
        ans = min(cur)
    else:ans = 0
    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()
N, M = map(int, input().split())
A = list(map(int, input().split()))
vote_sum = sum(A)
cnt = 0
y = "Yes"
n = "No"

for i in range(N):
	if (A[i]*4*M) >= vote_sum:
		cnt += 1
	if cnt == M:
		print(y)
		break
		
if C < M:
	print(n)

### FIXED CODE ###

from collections import deque
K = int(input())

q = deque([i for i in range(1, 10)])

for i in range(K):
    x = q.popleft()
    amari = x%10
    if amari == 0:
        l, m = 10*x, 10*x+1
        q.append(l)
        q.append(m)
    elif amari == 1:
        l, m, r = x*10, x*10+1, x*10+2
        q.append(l)
        q.append(m)
        q.append(r)
    elif amari == 9:
        l, m = 10*x+8, 10*x+9
        q.append(l)
        q.append(m)
    else:
        l, m, r = 10*x+(amari-1), 10*x+(amari), 10*x+(amari+1)
        q.append(l)
        q.append(m)
        q.append(r)

print(x)
n,d=map(int,input().split())
if n%(2*d+1)!=0:
   print(n//(2*d+1)+1)
else:
    print(n//(2*d+1

### FIXED CODE ###

n,d=map(int,input().split())
if n%(2*d+1)!=0:
   print(n//(2*d+1)+1)
else:
    print(n//(2*d+1))
l = input().split()
print(l[0] + l[1]/2)

### FIXED CODE ###

x, y = map(int, input().split())
print(x + y//2)
N,M = map(int, input().split())
el = {}
for i in range(N):
    P = list(map(int, input().split())).pop(0)
    if i == 0: el = set(P)
    el = el & set(P)
print(len(el))

### FIXED CODE ###

N,M = map(int, input().split())
el = {}
for i in range(N):
    P = list(map(int, input().split()))
    K = P.pop(0)
    if i == 0: el = set(P)
    el = el & set(P)
print(len(el))
import sys
input=sys.stdin.readline
S=list(input())
le=len(S)
dp=[[0 for i in range(13)] for j in range(le+1)]
dp[0][0] = 1

def xin(A,n):
    li=[0]*13
    for i in range(13):
        li[(i+n)%13] = A[i]%(10**9+7)
    return li


i=0
for k in reversed(S):
    if k=='?':
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s * 10**(i) + j) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(k * 10**(i) + j) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))


### FIXED CODE ###

S = [int(x) if x != '?' else - 1 for x in input()]
le=len(S)

dp = [[0]*13 for i in range(le+1)]
dp[0][0] = 1

i=0
for k in S:
    if k==-1:
        for s in range(10):
            for j in range(13):
                dp[i + 1][(s + j*10) % 13] += dp[i][j]%(10**9+7)

    else:
        k=int(k)
        for j in range(13):
            dp[i + 1][(j *10 + k) % 13] += dp[i][j]%(10**9+7)
        
    i += 1


print(dp[le][5]%(10**9+7))
N,K(int,input().split())
print(N%K)

### FIXED CODE ###

n,k=map(int,input().split())
if n%k==0:
    print(0)
else:
    print(1)
x1, x2, x3, x4, x5 = int(input().split())
x = list()
x.append(x1)
x.append(x2)
x.append(x3)
x.append(x4)
x.append(x5)
ans = 0
for i, j in enumerate(x):
  if i+1 != j
  ans = j
print(j)


### FIXED CODE ###

x1, x2, x3, x4, x5 = input().split()
x = list()
x.append(x1)
x.append(x2)
x.append(x3)
x.append(x4)
x.append(x5)
ans = 0
for i, j in enumerate(x):
  if int(j) == 0:
  	ans = i+1
print(int(ans))
a,b=map(int,input().split())
if a<b:
    print ('a') for i in range(b)
else:
    print ('b') for i in range(a)
    


### FIXED CODE ###

a,b=map(int,input().split())
if a<b:
    ans=str(a)*b
else:
    ans=str(b)*a
print(ans)
a,b,c,d=map(int,input().split())

if (abs(a-b)=<d)or(abs(a-c)=<d)or(abs(b-c)=<d):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

if ((abs(a-b)<=d)and(abs(b-c)<=d))or(abs(a-c)<=d):
    print("Yes")
else:
    print("No")
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i-j < 0:
            continue
        if i == j and dp[i-j] == 0:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

### FIXED CODE ###

n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i-j < 0:
            pass
        elif i == j:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

ans = ''
ans_digit = dp[n]
while len(ans) < ans_digit:
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                ans += str(i)
                break
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    n -= dic[i]
                    break
    
print(ans)
import sys
sys.setrecursionlimit(1000000)
mod=1000000007

class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


N,K=list(map(int,input().split()))
cache=[0 for i in range(K-2)]
cache[0]=1
for i in range(1,K-2):
    cache[i]=cache[i-1]*(K-1-i)%mod
cache.append(cache[-1])
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(1000000)
mod=1000000007
class Node:
    def __init__(self):
        self.next=[]
    def get_data(self,new_next,weight=1):
        self.next.append(new_next)
def BFS(i,depth,K):  
    depth+=1
    tmp=i
    seki=1
    num=len(tmp)
    if depth==1:
        calc=K-1
        loop=range(calc,calc-num,-1)
        for i in loop:
            seki*=i%1000000007

        
    else:
        calc=K-2
        num-=1
        if calc>=num:
            seki=cache[num]
        else:
            print(0)
            exit()

            
            
    for each in tmp:
        if not check_node[each]:
            check_node[each]=True
            seki*=BFS(node[each].next,depth,K)%mod
    return seki


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

if K>2:
    cache=[0 for i in range(K-2)]
    cache[0]=1
    for i in range(1,K-2):
        cache[i]=cache[i-1]*(K-1-i)%mod
    cache.append(cache[-1])
else:
    cache=[1,1]
node=[Node() for _ in range(N)]
check_node=[False for _ in range(N)]
check_node[0]=True
for i in range(N-1):
    p,n=list(map(int,input().split()))
    node[n-1].get_data(p-1)
    node[p-1].get_data(n-1)
start=0
d=0

com=K*BFS(node[0].next,d,K)
print(int(com)%mod)