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

import math 
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = ["pairwise coprime", "setwise coprime ", "not coprime"]

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
if gcd_list(A) != 1:
  print(ans[2])
  quit()
  
def seachPrimeNum(N):
    max = int(N ** (1 / 2))
    D = [0] * N
    D[0] = 1
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        nn = seachList[0]
        D[nn - 1] = nn
        primeNum.append(nn)
        tmp = nn
        for i in seachList:
          if i != nn:
            if i % tmp == 0:
              D[i - 1] = nn
        seachList = [i for i in seachList if i % tmp != 0]
    for i in seachList:
      D[i - 1] = i
    primeNum.extend(seachList)
    
    return primeNum, D  
  
primeNum, D = seachPrimeNum(1000000)
used = [0] * len(primeNum)

for i in range(N):
  now = A[i]
  q = [now]
  #print(now, D[now - 1])
  while now != D[now - 1]:
    now = int(now / D[now - 1])
    if now in primeNum:
      q.append(now)
  for i in q:
    if i in primeNum:
      if used[primeNum.index(i)] == 0:
        used[primeNum.index(i)] = 1
      else:
        print(ans[1])
        quit()  

print(ans[0])


### FIXED CODE ###

from math import gcd
n = int(input())
a = [int(i) for i in input().split()]

g = a[0]
for i in range(n):
    g = gcd(g,a[i])
if g != 1:
    print("not coprime")
    exit()

m = max(a)
fac = [1]*(m+1)
for i in range(2,m+1):
    if fac[i] != 1:
      continue
    for j in range(i,m+1,i):
      fac[j] = i
      
s = set()
for i in range(n):
    x = fac[a[i]]
    if x == 1: 
      continue
    if x in s:
      print("setwise coprime")
      exit()
    s.add(x)
print("pairwise coprime")
### BUGGY CODE ###

# D - String Formation
s = [x for x in input()]
q = int(input())
odd = 0
for i in range(q):
    t,*fc = input().split()
    if t=='1': odd ^= 1 #t1
    else: #t2
        if odd ^ (int(fc[0])-1): s = s+[fc[1]]
        else: s = [fc[1]] + s
print(*s[::-1] if odd else s,sep='')

### FIXED CODE ###

# D - String Formation
s = input()
q = int(input())
f = ''
b = ''
c = 0
for i in range(q):
    query = input().split()
    if query[0]=='1': c += 1 #t1
    else: #t2
        if c%2: #odd:reverse
            if query[1]=='1': #f1
                b += query[2]
            else: #f2
                f += query[2]
        else: #even
            if query[1]=='1': #f1
                f += query[2]
            else: #f2
                b += query[2]

if c%2: print(b[::-1] + s[::-1] + f) #odd
else: print(f[::-1] + s + b) #even
### BUGGY CODE ###

def main():
    n = int(input())
    # h, w, k = map(int, input().split())
    # a = list(map(int, input().split()))
    # s = input()
    while True:
        c = 360
        if c % n == 0:
            print(c // n)
            exit()
        c += 360


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    # n = int(input())
    # h, w, k = map(int, input().split())
    # a = list(map(int, input().split()))
    # s = input()
    x = int(input())
    i = 1
    while (x*i) % 360 != 0:
        i += 1
    print(i)


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

N = int(input())
X = input()
ans = 0
r=0
g=0
b=0
G = []
R = []
B = []
for i in range(0,N):
    if(X[i] == 'G'):
        G.append(i)
        g+=1
for k in range(0,N):
    if(X[k] == 'R'):
        R.append(k)
        r+=1
for j in range(0,N):
    if(X[j] == 'B'):
        B.append(j)
        b+=1
ans = r*b*g
for i in G:
    for k in R:
        for j in B:
            if(i<k):
                if(k<j):
                    if(j-k == k-i):
                        ans -=1
                else:
                    if(i<j):
                        if(k-j == j-i):
                            ans -=1
                    else:
                        if(k-i == i-j):
                            ans -= 1
            else:
                if(i<j):
                    if(j-i == i-k):
                        ans -=1
                else:
                    if(k<j):
                        if(i-j == j-k):
                            ans -= 1
                    else:
                        if(i-k == k-j):
                            ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
X = input()
ans = 0
r=0
g=0
b=0
G = []
R = []
B = []
for i in range(0,N):
    if(X[i] == 'G'):
        G.append(i)
        g+=1
for k in range(0,N):
    if(X[k] == 'R'):
        R.append(k)
        r+=1
for j in range(0,N):
    if(X[j] == 'B'):
        B.append(j)
        b+=1
ans = r*b*g
for i in range(0,N):
    for j in range(i+1,N):
        if(2*j-i < N) and X[i] != X[j]:
            if(X[2*j-i] != X[i]) and (X[2*j-i] != X[j]):
                ans -= 1
print(ans)
### BUGGY CODE ###

from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = [input() for _ in range(h)]
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            q = deque([(i, j, 0)])
            v = set()
            while q:
                ii, jj, cnt = q.popleft()
                v.add((ii, jj))
                ret = max(ret, cnt)
                for d_ii, d_jj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    n_ii = ii + d_ii
                    n_jj = jj + d_jj
                    if n_ii >= h or n_jj >= w or n_ii < 0 or n_jj < 0:
                        continue
                    if g[n_ii][n_jj] == '#' or (n_ii, n_jj) in v:
                        continue
                    q.append((n_ii, n_jj, cnt + 1))
                # n_ii =
                # # ↓
                # if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                #     q.append((ii + 1, jj, cnt + 1))
                # # →
                # if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                #     q.append((ii, jj + 1, cnt + 1))
                # # ↑
                # if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                #     q.append((ii - 1, jj, cnt + 1))
                # # ←
                # if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                #     q.append((ii, jj - 1, cnt + 1))
    return ret


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
from typing import List


def main():
    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        r = list(input())
        g.append(r)
    print(mm(h, w, g))


def mm(h: int, w: int, g: List[List[str]]) -> int:
    ret = 0
    for i in range(h):
        for j in range(w):
            if (g[i][j] == '#'):
                continue
            v = set()
            q = deque([(i, j, 0)])
            v.add((i, j))
            while q:
                ii, jj, cnt = q.popleft()
                ret = max(ret, cnt)
                # ↓
                if ii < h - 1 and g[ii + 1][jj] == '.' and (ii + 1, jj) not in v:
                    q.append((ii + 1, jj, cnt + 1))
                    v.add((ii + 1, jj))
                # →
                if jj < w - 1 and g[ii][jj + 1] == '.' and (ii, jj + 1) not in v:
                    q.append((ii, jj + 1, cnt + 1))
                    v.add((ii, jj + 1))
                # ↑
                if ii > 0 and g[ii - 1][jj] == '.' and (ii - 1, jj) not in v:
                    q.append((ii - 1, jj, cnt + 1))
                    v.add((ii - 1, jj))
                # ←
                if jj > 0 and g[ii][jj - 1] == '.' and (ii, jj - 1) not in v:
                    q.append((ii, jj - 1, cnt + 1))
                    v.add((ii, jj - 1))
    return ret


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

#C
#入力
N=int(input())
A=list(map(int,input().split()))

#処理
t=0
while len(A)!=0:
    x=A[0]
    A=A[1:]
    for i in A:
        if x==i:
            print("NO")
            t=1
            break
if t==0:
    print("YES")

### FIXED CODE ###

#C
#入力
N=int(input())
A=list(map(int,input().split()))

#処理

A.sort()
t=0
for i in range(N-1):
    if A[i]==A[i+1]:
        print("NO")
        t=1
        break
if t==0:
    print("YES")
### BUGGY CODE ###

number = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(number):
    for j in range(i,number):
        if a[i] ==j+1 and a[j] == i+1:
            count += 1
print(int(count))

### FIXED CODE ###

number = int(input())
a = list(map(int,input().split()))
count = 0
for i in range(number):
    j = a[i]-1
    if a[j] == i + 1:
        count += 1
print(int(count/2))
### BUGGY CODE ###

from collections import Counter


def is_divideable(a, nums):
    x = 1
    while x ** 2 <= a:
        if a % x == 0:
            if x in nums or (a // x) in nums:
                return True
        x += 1
    return False


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    nums = set()
    A.sort()
    ans = 0
    for a in A:
        if cnt[a] == 1 and not is_divideable(a, nums):
            ans += 1
        nums.add(a)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX = max(A)
    dp = [True] * (MAX+1)
    A.sort()
    cnt = Counter(A)
    ans = 0
    for a in A:
        if dp[a]:
            if cnt[a] == 1:
                ans += 1
            x = a
            while x <= MAX:
                dp[x] = False
                x += a
    print(ans)


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

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans=1
n=int(f.readline().strip())
prime=[]
# Start from where n is equal to 2
for _ in range(1,n):
    number_of_multiply=[]
    tmp=_+1
    num_of_divisor=1
    for __ in prime:
        cnt=0
        if tmp==1:
            break
        while (tmp%__)==0:
            cnt+=1;tmp//=__;
        if cnt>0:
            num_of_divisor*=cnt+1
    if num_of_divisor==1:
        prime.append(_+1)
        ans+=(_+1)*2
    else:
        ans+=(_+1)*num_of_divisor
print(ans)

### FIXED CODE ###

import sys
#DEBUG=True
DEBUG=False
if DEBUG:
    f=open("202006_5th/D_input.txt")
else:
    f=sys.stdin
ans_sum=0
n=int(f.readline().strip())
for _ in range(1,n+1):
    num=n//_
    ans_sum+=_*((num*(num+1))//2)
print(ans_sum)
### BUGGY CODE ###

word_number, questions_number = map(int, input().split())
# words = list(input())
words = input()
questions = []
for question in range(questions_number):
    a,b = map(int, input().split())
    questions.append([a-1, b-1])

for i in range(len(questions)):
    counter = 0
    for j in range(questions[i][0], questions[i][1]):
        # if words[j] == "A" and words[j+1] == "C":
        if words[j: j+2] == "AC":
            counter += 1
    print(counter)


### FIXED CODE ###

word_number, questions_number = map(int, input().split())
# words = list(input())
words = input()
questions = []
for question in range(questions_number):
    a,b = map(int, input().split())
    questions.append([a-1, b-1])

# 複数回の問題を2秒以内はきついので前処理する必要あり
# for i in range(len(questions)):
#     counter = 0
#     for j in range(questions[i][0], questions[i][1]):
#         # if words[j] == "A" and words[j+1] == "C":
#         if words[j: j+2] == "AC":
#             counter += 1
#     print(counter)

hasAC = [0] * word_number
for i in range(word_number-1):
    if words[i: i+2] == "AC":
        hasAC[i+1] = hasAC[i] + 1
    else:
        hasAC[i+1] = hasAC[i]

for i in range(questions_number):
    print(hasAC[questions[i][1]] - hasAC[questions[i][0]])
### BUGGY CODE ###

w,h= map(int, raw_input().split())
p =[]
q = []
for i in xrange(w):
    t = input()
    p.append(t)

for i in xrange(h):
    t = input()
    q.append(t)
c = sum(p) + sum(q)
for i in xrange(h):
    for j in xrange(w):
        c += min(p[j], q[i])
print c

### FIXED CODE ###

w,h= map(int, raw_input().split())
p =[]
q = []
for i in xrange(w):
    t = input()
    p.append(t)

for i in xrange(h):
    t = input()
    q.append(t)
p =sorted(p,reverse=True)
q =sorted(q, reverse=True)
ac = p[:]
acq = q[:]
i = w-2
while i >=0:
    ac[i] += ac[i+1]
    i -=1
i = h - 2
while i >= 0:
    acq[i] += acq[i + 1]
    i -= 1
c = ac[0] + acq[0]
k = 0
# for i in xrange(h):
i = 0
while i < h:
    # for j in xrange(k,w):
        j = k
        # print i,j
        if j >= w:
            break
        if q[i] > p[j]:
            c += ac[j]
            i += 1
            # break
        else:
            c +=acq[i]
            k +=1
        # c += q[i]
print c
### BUGGY CODE ###

n, *d = map(int, open(0).read().split())
s = [b-a for a,b in zip(d[:n],d[n:]) if b>a]
m = c = 0
if s:
  for i in sorted(a-b for a,b in zip(d[:n],d[n:]) if a>=b)[::-1]:
    m += i
    c += 1
    if sum(s)<=m:
      print(len(s)+c)
      exit()
  print(-1)
else:
  print(0)

### FIXED CODE ###

n,*d=map(int,open(0).read().split())
f=[d[i]-d[n+i]for i in range(n)]
m=[v for v in f if v<0];p=sorted(v for v in f if v>0)
c=len(m);s=sum(m)
while s<0and p:s+=p.pop();c+=1
print([c,-1][s<0])
### BUGGY CODE ###

n , k , q = map(int, input().split())
a = [int(input()) for i in range(q)]
points = [k - q]*n
for i in range(n):
    points[i] += a.count(i+1)
    if points[i] >= 1:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n , k , q = map(int, input().split())
points = [k - q] * n
for i in range(q):
    c = int(input())
    points[c-1] += 1
for i in range(n):
    if points[i] >= 1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
if a[0] >= K:
    print(0)
    exit()

a = [a[i] for i in range(N) if a[i]<K]
a.reverse()
N = len(a)
ans = N
dp = [False]*K
dp[0] = True
Smax = 0
for i,a_ in enumerate(a):
    if Smax + a_ >= K:
        ans = i
    updated = True
    for j in range(min(Smax,K-a_-1),-1,-1):
        if dp[j]:
            dp[j+a_]=True
            if updated:
                Smax = max(Smax,j+a_)
                updated = False
if ans != N:
    ans = N-ans-1

print(ans)

### FIXED CODE ###

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

def f(N,K,a):
    a.sort()
    if a[0] >= K:
        print(0)
        exit()

    a = [a[i] for i in range(N) if a[i]<K]
    N = len(a)
    ans = N
    dp = [False]*K
    dp[0] = True
    Smax = 0
    for i,a_ in reversed(list(enumerate(a))):
        if Smax + a_ >= K:
            ans = i
        updated = True
        for j in range(min(Smax,K-a_-1),-1,-1):
            if dp[j]:
                dp[j+a_]=True
                if updated:
                    Smax = max(Smax,j+a_)
                    updated = False
    return ans

print(f(N,K,a))
### BUGGY CODE ###

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

a.sort()

l = 0
r = n

while l < r:
    m = (l + r) // 2
    if a[m] >= k:
        r = m
        continue
    dp = [[0 for _ in range(k)] for _ in range(n)]
    dp[0][0] = 1
    t = 1
    check = 0
    for i in range(n):
        if i == m:
            continue
        for j in range(k - a[i]):
            if dp[t - 1][j] == 1:
                dp[t][j] = 1
                temp = j + a[i]
                if k - a[m] <= temp < k:
                    check = 1
                    break
                elif temp < k - a[m]:
                    dp[t][temp] = 1
        if check == 1:
            break
        t += 1
    if check == 0:
        l = m + 1
    else:
        r = m

print(l)

### FIXED CODE ###

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

a.sort(reverse=True)

temp = 0
ans = 0

for x in a:
    if temp + x < k:
        temp += x
        ans += 1
    else:
        ans = 0

print(ans)
### BUGGY CODE ###

import bisect

N=int(input())
L=list(map(int,input().split()))
L.sort()

ans=0

def find_gt(a,x):
    i = bisect.bisect_right(a,x)
    if i != len(a):
        return i
    return(-1)

for i in range(N-1,-1,-1):
    for j in range(i-1,-1,-1):
        l=L[:j]
        if len(l)>=1:
            num=find_gt(l,L[i]-L[j])
            if num!=-1:
                ans+=len(l)-num
        else:
            continue


print(ans)

### FIXED CODE ###

import bisect

N=int(input())
L=list(map(int,input().split()))
L.sort()
count=0

for i in range(N):
    for j in range(i+1,N):
        T=bisect.bisect_left(L,L[i]+L[j])
        count+=T-j-1
print(count)
### BUGGY CODE ###

def solve():
    MOD = 10**9 + 7

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

    Sss = [[] for _ in range(N+1)]
    for S in range(1<<N):
        num1 = bin(S).count('1')
        Sss[num1].append(S)

    dp = [0] * (1<<N)
    dp[0] = 1
    for iM, Ss in enumerate(Sss[:-1]):
        for S in Ss:
            dp[S] %= MOD
            for iW in range(N):
                if S & (1<<iW) == 0 and Ass[iM][iW]:
                    S2 = S | (1<<iW)
                    dp[S2] += dp[S]

    print(dp[-1] % MOD)


solve()


### FIXED CODE ###

MOD = 10**9 + 7

N = int(input())
As = [int(input().replace(' ', ''), 2) for _ in range(N)]

patWsList = [[] for _ in range(N+1)]
for patW in range(2**N):
    num1 = sum([(patW >> i) & 1 for i in range(N)])
    patWsList[num1].append(patW)

dp = [0] * (2**N)
dp[-1] = 1
for iM, (A, patWs) in enumerate(zip(As, reversed(patWsList))):
    for patW in patWs:
        A2 = A & patW
        dpNow = dp[patW]
        for iW in range(N):
            if A2 & (1 << iW):
                dp[patW ^ (1 << iW)] += dpNow
                dp[patW ^ (1 << iW)] %= MOD

print(dp[0])
### BUGGY CODE ###


import numpy as np
N = int(input())
As=input().split()
A = np.array([int(s) for s in As])
del(As)

min2A = A[A.argsort()[1]]
minA = np.amin(A)
if np.sum((A%min2A)==0)>=N-1:
    print(min2A)
elif np.sum((A%minA)==0)>=N-1:
    print(minA)
else:
    for i in range((min2A//2)+1)[::-1]:
        if np.sum((A%i)==0)>=N-1:
            print(i)
            break



### FIXED CODE ###


import numpy as np
N = int(input())
As=input().split()
A = np.array([int(s) for s in As])
del(As)

min2A = A[A.argsort()[1]]
minA = np.amin(A)
if np.sum((A%min2A)==0)>=N-1:
    print(min2A)
elif np.sum((A%minA)==0)>=N-1:
    print(minA)
else:
    for i in range(2,min2A+1):
        if (min2A%i == 0) or (minA%i == 0):
            if(min2A%i == 0):
                j = int(min2A/i)
            elif(minA%i == 0):
                j=int(minA/i)
            if np.sum((A%j)==0)>=N-1:
                print(j)
                break
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    l = [0]*X*Y
    for i in range(X):
        for j in range(Y):
            l[i+j*X] = A[i]+B[j]

    l.sort(reverse=True)
    t = min(3000,X*Y)
    l = l[:t]

    ans = [0] * (t) * Z
    for i in range(t):
        for j in range(Z):
            ans[i+j*t] = l[i] + C[j]

    ans.sort(reverse=True)
    for i in range(K):
        print(ans[i])


    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(X) ]  # type: "List[int]"
    B = [ int(next(tokens)) for _ in range(Y) ]  # type: "List[int]"
    C = [ int(next(tokens)) for _ in range(Z) ]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    l = [0]*X*Y
    for i in range(X):
        for j in range(Y):
            l[i+j*X] = A[i]+B[j]

    l.sort(reverse=True)
    t = min(3000,X*Y)
    l = l[:t]

    ans = [0] * (t) * Z
    for i in range(t):
        for j in range(Z):
            ans[i+j*t] = l[i] + C[j]

    ans.sort(reverse=True)
    for i in range(K):
        print(ans[i])


    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(X) ]  # type: "List[int]"
    B = [ int(next(tokens)) for _ in range(Y) ]  # type: "List[int]"
    C = [ int(next(tokens)) for _ in range(Z) ]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

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

from copy import deepcopy
from sys import stdin

def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
def LS(): return list(stdin.readline().rstrip().split())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return r

n = I()
s = S()

ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        if s[i] != s[j]:
            for k in range(j+1,n):
                if s[k] != s[i] and s[k] != s[j]:
                    if j-i != k-j:
                        ans += 1

print(ans)

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
 
n = I()
s = list(S())

r = s.count('R')
g = s.count('G')
b = s.count('B')
 
ans = r*g*b
for i in range(n-1):
    for j in range(1,n):
        if i-j<0 or n<=i+j:
            break
        else:
            if s[i-j]!=s[i] and s[i]!=s[i+j] and s[i-j]!=s[i+j]:
                ans-=1
 
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

ans = 1
for i in range(n):
    ans = ans * a[i]

if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

fflag = False
for i in range(n):
    if a[i] == 0:
        fflag = True
        break

ans = 1
flag = True
for i in range(n):
    if fflag == True:
        ans = 0
        break
    ans = ans * a[i]
    if ans == 0:
        break
    if ans > 1000000000000000000:
        print(-1)
        flag = False
        break

if flag == True:
    print(ans)
### BUGGY CODE ###

import operator as op
from functools import reduce
 
def npr(n, r):
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    return numer


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

child_num = [0 for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    child_num[a] += 1
    child_num[b] += 1

for i in range(1, N):
    child_num[i] -= 1

# calculate
min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)

### FIXED CODE ###

import operator as op
from functools import reduce
 
def npr(n, r):
    numer = 1
    for k in range(r):
        numer = numer * (n - k)
        numer %= q
    return numer


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

child_num = [0 for i in range(N)]
for k in range(N - 1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    child_num[a] += 1
    child_num[b] += 1

for i in range(1, N):
    child_num[i] -= 1

# calculate
min_child = min(child_num)
if K < min_child:
    print(0)
else:
    ans = (K * npr(K - 1, child_num[0])) % q
    for i in range(1, N):
        val = npr(K - 2, child_num[i]) % q
        ans = (ans * val) % q
    print(ans)