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

import math
def isPrime(n, primes):
    if n == 2:
        return True
    if n%2 == 0:
        return False
    nMax = int(math.sqrt(n))+1
    for i in range(3, nMax+1):
        if n%i == 0: return False
    else:
        primes.append(n)
        return True
         
while 1:
    try:
        n = input()
        c = 0
        for i in range(2,n+1):
            p = [2]
            if isPrime(i, p) is True:
                c += 1
        print c
    except EOFError:
        break

### FIXED CODE ###

n = 10**6
c = 0
ps = [False]*(n+1)
for i in xrange(2, n+1):
    if i%2 != 0 or i == 2:
        ps[i] = True
for i in xrange(2, int(n**0.5+1)):
    if ps[i]:
        for j in xrange(i**2, n+1, i):
            ps[j] = False

while 1:
    try:
        n = input()
        if n == 2: print 1
        else: print len([0 for i in xrange(2, n+1) if ps[i]])
    except EOFError:
        break
### BUGGY CODE ###

N = int(input())
S = list(input())

Rcnt = 0
Gcnt = 0

excep = 0

for i in S:
    if i == 'R':
        Rcnt += 1
    elif i == 'G':
        Gcnt += 1

for i in range(len(S)):
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                # print(S[i], S[i+1], S[i+2])
                excep += 1

RGBcalc = Rcnt * Gcnt * (N - Rcnt - Gcnt)

print(RGBcalc - excep)

### FIXED CODE ###



N = int(input())
S = list(input())

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                excep += 1
        elif i+j+j >= len(S):
            break

print(Rcnt * Gcnt * (N - Rcnt - Gcnt) - excep)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
contain_one = [[i, j] for i, j in ab if i == 1]
contain_n = [[k, l] for k, l in ab if l == n]

for a, b in contain_one:
    second = b
    for c, d in contain_n:
        if c == second:
            print("POSSIBLE")
            exit()
else:
    print("IMPOSSIBLE")




### FIXED CODE ###

n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        ab.append(b)
    if b == n:
        ab.append(a)

if len(ab) != len(set(ab)):
        print("POSSIBLE")
        exit()
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import math
from collections import Counter

def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors


def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = Counter(A)
    b = set(A)
    c = {}
    def find(x):
        if x in c:
            return c[x]
        l = make_divisors(x)
        for j in l:
            if j == x:
                if a[j] > 1:
                    c[x] = 0
                    return 0
            else:
                if j in b:
                    c[x] = 0
                    return 0
        c[x] = 1
        return 1
    r = 0
    for i in A:
        r += find(i)
    return r
print(main())


### FIXED CODE ###

#dame datta....
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = sorted(A)
    a = Counter(A)
    l = [0] * (10**6+1)
    v = [0] * (10**6+1)
    for i in B:
        if v[i] == 1 or l[i] == 1:
            continue
        else:
            v[i] = 1
        t = 2*i
        while t < 10**6 + 1:
            l[t] = 1
            t += i
    r = 0
    for i in A:
        if l[i] == 0 and a[i] == 1:
            r += 1
    return r
print(main())
### BUGGY CODE ###

import numpy as np
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)

for i in range(0,M):
    A[0]=int(A[0]/2)
    flag=0
    while(flag!=1):
        for j in range(0,N-1):
            if(A[j]>A[j+1]):
                flag=1
                break
            else:
                tmp=A[j]
                A[j]=A[j+1]
                A[j+1]=tmp
        
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)
    
for i in range(0,M):
    tmp=heapq.heappop(A)
    heapq.heappush(A,-int(-tmp/2))
print(-sum(A))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = LIST()

a_cnt = Counter(a)
num_1 = a_cnt[1]
num_2 = a_cnt[2]
num_3 = a_cnt[3]

dp = [[[0]*(302) for _ in range(302)] for _ in range(302)]

@lru_cache(maxsize=None)
def rec(i, j, k):
	if i==0 and j==0 and k==0: return 0.0
	if dp[i][j][k]: return dp[i][j][k]

	res = 0
	if i > 0: res += rec(i-1, j, k)*i
	if j > 0: res += rec(i+1, j-1, k)*j
	if k > 0: res += rec(i, j+1, k-1)*k
	res += N
	res /= (i+j+k)
	dp[i][j][k] = res
	return res

print(rec(num_1, num_2, num_3))


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = LIST()

a_cnt = Counter(a)
num_1 = a_cnt[1]
num_2 = a_cnt[2]
num_3 = a_cnt[3]

dp = [[[0.0]*(301) for i in range(301)] for j in range(301)]
 
for i in range(1, N+1):
    for j in range(min(i, num_2+num_3)+1):
        for k in range(min(j, num_3)+1):
            s = i-j
            t = j-k
            res = 0
            if s > 0:
                res += dp[s-1][t][k]*s  
            if t > 0:
                res += dp[s+1][t-1][k]*t
            if k > 0:
                res += dp[s][t+1][k-1]*k
            res += N
            res /= (s+t+k)

            dp[s][t][k] = res

print(dp[num_1][num_2][num_3])
### BUGGY CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
       
for i in range(Q):
    tmp = 0
    now = LR[i][0]
    now_state = number_dict[now]
    
    while True:
        if now == LR[i][1]:
            break
        
        tmp += abs(number_dict[now+D][0] - now_state[0]) + abs(number_dict[now+D][1] - now_state[1])
        now = now + D
        now_state = number_dict[now]
        

            
    print(tmp)
        



### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
        
number = [0 for _ in range(H*W+1)]
for i in range(H*W):
    now = H * W - i
    
    if now + D > H * W:
        pass
    
    else:
        number[now] = number[now + D] + abs(number_dict[now+D][0] - number_dict[now][0]) + abs(number_dict[now+D][1] - number_dict[now][1])
       

for i in range(Q):
    res = number[LR[i][0]] - number[LR[i][1]]
            
    print(res)
### BUGGY CODE ###

import math
import functools
 

@functools.lru_cache(maxsize=8128)
def nCr(n,r):
    if n<r:
        return 0
    
    result = math.factorial(n)//math.factorial(r)//math.factorial(n-r)
    return result

def compute(count):
    total = 0
    for i in count:
        total += nCr(i,2)
    return total


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

count = [0] * (N+1)

for value in data:
    count[value] += 1
    

for i in range(len(data)):
    count[data[i]] -= 1
    
    total = compute(count)
    print(total)
          
          
    count[data[i]] += 1


### FIXED CODE ###

import math
 


def nC2(i):
    if i<=1:
        return 0
    return i*(i-1)//2

def compute(count):
    total = 0
    for i in count:
        total += nC2(i)
    return total


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

count = [0] * (N+1)

for value in data:
    count[value] += 1
    
    
total = compute(count)    

for value in data:
    remove = nC2(count[value])
    add = nC2(count[value]-1)

    print(total-remove+add)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def create_graph(N, edge_pairs, is_bi_dir=False):
    in_vs, out_vs, weights = [], [], []
    for s, t, w in edge_pairs:
        in_vs.append(s)
        out_vs.append(t)
        weights.append(w)
        if is_bi_dir:
            in_vs.append(t)
            out_vs.append(s)
            weights.append(w)
    return csr_matrix((weights, (in_vs, out_vs)), shape=(N, N), dtype=np.int64)


N, M, L = map(int, input().split())
edge_pairs = []
for _ in range(M):
    s, t, w = map(int, input().split())
    edge_pairs.append((s-1, t-1, w))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph)
edge_pairs = []
for i in range(N):
    for j in range(i+1, N):
        if dist[i][j] <= L:
            edge_pairs.append((i, j, 1))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if np.isinf(ans):
        print(-1)
    else:
        print(int(ans - 1))


### FIXED CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def create_graph(N, edge_pairs, is_bi_dir=False):
    in_vs, out_vs, weights = [], [], []
    for s, t, w in edge_pairs:
        in_vs.append(s)
        out_vs.append(t)
        weights.append(w)
        if is_bi_dir:
            in_vs.append(t)
            out_vs.append(s)
            weights.append(w)
    return csr_matrix((weights, (in_vs, out_vs)), shape=(N, N), dtype=np.int64)


N, M, L = map(int, input().split())
edge_pairs = []
for _ in range(M):
    s, t, w = map(int, input().split())
    edge_pairs.append((s-1, t-1, w))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph, directed=False)
edge_pairs = []
for i in range(N):
    for j in range(i+1, N):
        if dist[i][j] <= L:
            edge_pairs.append((i, j, 1))
graph = create_graph(N, edge_pairs, True)
dist = floyd_warshall(graph, directed=False)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dist[s-1][t-1]
    if np.isinf(ans):
        print(-1)
    else:
        print(int(ans - 1))
### BUGGY CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    S = input()
    answer = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if (S[i], S[j]) == ("G", "R") or (S[i], S[j]) == ("R", "G"):
                answer += S[j + 1 :].count("B")
                if 2 * j - i < N:
                    if S[2 * j - i] == "B":
                        answer -= 1
            elif (S[i], S[j]) == ("G", "B") or (S[i], S[j]) == ("B", "G"):
                answer += S[j + 1 :].count("R")
                if 2 * j - i < N:
                    if S[2 * j - i] == "R":
                        answer -= 1
            elif (S[i], S[j]) == ("B", "R") or (S[i], S[j]) == ("R", "B"):
                answer += S[j + 1 :].count("G")
                if 2 * j - i < N:
                    if S[2 * j - i] == "G":
                        answer -= 1
    print(answer)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    S = input()
    C = Counter(S)
    R = C.get("R", 0)
    G = C.get("G", 0)
    B = C.get("B", 0)
    ans = R * G * B
    for left in range(N):
        for mid in range(left + 1, N):
            right = mid + mid - left
            if right < N:
                if S[right] != S[mid] and S[mid] != S[left] and S[right] != S[left]:
                    ans -= 1
    print(ans)


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

K=int(input())
import math
out=0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            out=out+math.gcd(i,math.gcd(j,k))
print(int(out))


### FIXED CODE ###

K=int(input())
import math
out=0

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            out=out+math.gcd(i,math.gcd(j,k))
print(int(out))
### BUGGY CODE ###

#C - Sum of product of pairs
N = int(input())
A = list(map(int,input().split()))
SUM = 0
MOD = 1000000007
for i in range(N-1):
    for j in range(1,N):
        if i < j:
            SUM = (SUM + (A[i] * A[j] % MOD) ) % MOD

# 出力
print(SUM)


### FIXED CODE ###

#C - Sum of product of pairs
N = int(input())
A = list(map(int,input().split()))
SUM = 0
jsum= 0
MOD = 1000000007
for j in range(N):
    jsum = (jsum + A[j]) % MOD

for i in range(N-1):
    jsum = (jsum - A[i]) % MOD
    SUM = ( SUM + (jsum * A[i] % MOD ) ) % MOD

# 出力
print(SUM)
### BUGGY CODE ###

import itertools
n = int(input())
s = list(input())
print(len(set(itertools.combinations(s, 3))))

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(1000):
    c = [str(i // 100), str((i // 10) % 10), str(i % 10)]
    t = 0
    for j in range(n):
        if s[j]==c[t]:
            t+=1
        if t==3:
            cnt+=1
            break
print(cnt)
### BUGGY CODE ###

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

if M % N == 0:
    print(M // N)
else:
    for x in range(min(M, 10 ** 9) + 1, 0, -1):
        if M % x == 0:
            if M / x >= N:
                print(x)
                exit()

### FIXED CODE ###

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

As = []
k = 1
while k * k <= M:
    if M % k == 0:
        As.append(k)
        As.append(M // k)
    k += 1

As = sorted(As, reverse=True)

for ans in As:
    if M // ans >= N:
        print(ans)
        break
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
to = [[] for i in range(N)]  # 隣接リスト
c = [0] * N

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


def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        c[u] += c[v]
        dfs(u, v)


for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    c[p] += x
dfs(0)
print(*c)


### FIXED CODE ###

import sys

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


def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        c[u] += c[v]
        dfs(u, v)


N, Q = map(int, input().split())
to = [[] for i in range(N)]  # 隣接リスト
c = [0] * N

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

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    c[p] += x
dfs(0)
print(*c)
### BUGGY CODE ###

def solve1():
	maxx = maxy = 0
	minx = miny = 1000111000
	for i in xrange(n):
		maxx = max(maxx, x[i])
		minx = min(minx, x[i])
		maxy = max(maxy, y[i])
		miny = min(miny, y[i])
	return (maxx-minx)*(maxy-miny)

def solve2a(minx):
	miny = min(x)
	maxy = max(y)
	maxx = 0
	
	for i in xrange(n):
		if y[i] < minx:
			return 2**60
		if minx <= x[i]:
			maxx = max(maxx, x[i])
		else:
			maxx = max(maxx, y[i])
	return (maxx-minx)*(maxy-miny)

def solve2():
	res = 2**60
	for minx in x:
		res = min(res, solve2a(minx))
	for minx in y:
		res = min(res, solve2a(minx))
	return res

n = int(raw_input())

x = [0]*n
y = [0]*n
mini = maxi = 0
for i in xrange(n):
	x[i],y[i] = map(int, raw_input().split())
	x[i],y[i] = min(x[i],y[i]),max(x[i],y[i])
	if x[i] < x[mini]:
		mini = i
	if y[maxi] < y[i]:
		maxi = i

ans = solve1()
if mini != maxi:
	ans = min(ans, solve2())
print ans


### FIXED CODE ###

def solve1():
	maxx = maxy = 0
	minx = miny = 1000111000
	for i in xrange(n):
		maxx = max(maxx, x[i])
		minx = min(minx, x[i])
		maxy = max(maxy, y[i])
		miny = min(miny, y[i])
	return (maxx-minx)*(maxy-miny)

def solve2a(minx):
	miny = min(x)
	maxy = max(y)
	maxx = 0
	
	for i in xrange(n):
		if y[i] < minx:
			return 2**60
		if minx <= x[i]:
			maxx = max(maxx, x[i])
		else:
			maxx = max(maxx, y[i])
	return (maxx-minx)*(maxy-miny)

def solve2_():
	res = 2**60
	for minx in x:
		res = min(res, solve2a(minx))
	for minx in y:
		res = min(res, solve2a(minx))
	return res

def solve2():
	res = 2**60
	xy = x+y
	xy.sort()
	miny = min(x)
	maxy = max(y)
	my = min(y)
	
	pi = 0
	for minx in xy:
		if my < minx:
			break
		while pi < n and p[pi][0] < minx:
			pi += 1
		maxx = max(ly[pi], rx[pi+1])
		res = min(res, (maxx-minx)*(maxy-miny))
	return res

n = int(raw_input())

x = [0]*n
y = [0]*n
p = [(0,0)]*n
mini = maxi = 0
for i in xrange(n):
	x[i],y[i] = map(int, raw_input().split())
	x[i],y[i] = min(x[i],y[i]),max(x[i],y[i])
	p[i] = x[i],y[i]
	if x[i] < x[mini]:
		mini = i
	if y[maxi] < y[i]:
		maxi = i
p.sort()
ly = [0]*(n+2)
rx = [0]*(n+2)
mx = my = 0
for i in xrange(n):
	my = max(my, p[i][1])
	ly[i+1] = my

for i in xrange(n-1,-1,-1):
	mx = max(mx, p[i][0])
	rx[i+1] = mx

ans = solve1()
if mini != maxi:
	ans = min(ans, solve2())
print ans
### BUGGY CODE ###

## coding: UTF-8
#最後の方のテストケースでREになってしまう。時間切れ。
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product

N = int(input())

s = input().split()
p = [int(w) for w in s]
#print('p:{}'.format(p))

number_list = []
'''
for i in range(N):
    counter = 0
    for j in range(N):
        if(p[j] == i+1):
            counter +=1
    number_list.append(counter)
'''
for i in range(N):
    #print(mylist.count("A"))
    number_list.append(p.count(i+1))
#print('number_list:{}'.format(number_list))

def n_C_2(n):
    if(n == -1):
        return 0
    else:
        return int(n * (n-1) / 2)


full_combi = []
pickup_combi = []
print_combi = []

for i in range(N):
    full_combi.append(n_C_2(number_list[i]))
    pickup_combi.append(n_C_2(number_list[i] - 1))
#print('full_combi:{}'.format(full_combi))
#print('pickup_combi:{}'.format(pickup_combi))

for i in range(N):
    print_combi.append(sum(full_combi) - full_combi[i] + pickup_combi[i])
#print('print_combi:{}'.format(print_combi))

for i in range(N):
    index = p[i] - 1
    print(print_combi[index])

### FIXED CODE ###

## coding: UTF-8
#最後の方のテストケースでREになってしまう。時間切れ。
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product

N = int(input())

s = input().split()
p = [int(w) for w in s]
#print('p:{}'.format(p))

number_list = [0 for i in range(N)]
'''
for i in range(N):
    counter = 0
    for j in range(N):
        if(p[j] == i+1):
            counter +=1
    number_list.append(counter)
'''
#print(number_list)

for i in range(N):
    number_list[p[i] - 1] += 1
#print(number_list)



def n_C_2(n):
    if(n == -1):
        return 0
    else:
        return int(n * (n-1) / 2)


full_combi = []
pickup_combi = []
print_combi = []

for i in range(N):
    full_combi.append(n_C_2(number_list[i]))
    pickup_combi.append(n_C_2(number_list[i] - 1))
#print('full_combi:{}'.format(full_combi))
#print('pickup_combi:{}'.format(pickup_combi))

all_full = sum(full_combi)
for i in range(N):
    print_combi.append(all_full - full_combi[i] + pickup_combi[i])
#print('print_combi:{}'.format(print_combi))

for i in range(N):
    index = p[i] - 1
    print(print_combi[index])
### BUGGY CODE ###

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

B = [1]
hop = 0
ans = 0
for n in range(N):
    nc = A[B[n]-1]    
    if nc in B:
        idx = B.index(nc)
        loop = B[idx:]
        break
    B.append(nc)
    K -= 1
    ans = nc
    if K < 1:
        break

if K > 0:
    L = len(loop)
    K = K % L
    K -= 1
    ans = loop[K]
print(ans)

### FIXED CODE ###

N,K = list(map(int, input().split()))
A = list(map(int, input().split()))
 
B = [1]
go = [0]*N
hop = 0
ans = 0
for n in range(N):
    nc = A[B[n]-1]
    if go[nc-1] == 1:
        idx = B.index(nc)
        loop = B[idx:]
        break
    B.append(nc)
    K -= 1
    go[nc-1] = 1
    ans = nc
    if K < 1:
        break
 
if K > 0:
    L = len(loop)
    K = K % L
    K -= 1
    ans = loop[K]
print(ans)
### BUGGY CODE ###

n = int(input())

x = list(map(int,input().split()))

ans = 1

for i in x:
  ans *= i
  
if ans>1000000000000000000:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())

x = list(map(int,input().split()))

limit = 10**18

ans = 1

q = 0

if 0 in x:
    ans = 0
else:
    for i in x:
        ans *= i
        if ans>limit:
            q = 1
            break
    
if q == 1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

N, M = [int(i) for i in input().strip().split(' ')]
A = [int(i) for i in input().strip().split(' ')]

for _ in range(M):
  b, c = [int(i) for i in input().strip().split(' ')]
  A.extend([c] * b)

A = sorted(A, reverse=True)

print(sum(A[:N]))

### FIXED CODE ###

from operator import itemgetter

N, M = [int(i) for i in input().strip().split(' ')]
A = [int(i) for i in input().strip().split(' ')]
A = sorted(A, reverse=True)

X = []
for _ in range(M):
  (b, c) = [int(i) for i in input().strip().split(' ')]
  X.append((b, c))

X = sorted(X, reverse=True, key=itemgetter(1))
if M < N:
  for _ in range(N - M):
    X.append((0, 0))

v = 0
ai = 0
xi = 0

while N > 0:
  a = A[ai]
  n, x = X[xi]
  if a > x:
    N -= 1
    ai += 1
    v += a
  else:
    if n > N:
      n = N
    N -= n
    xi += 1
    v += x * n

print(v)
### BUGGY CODE ###

n,k=map(int,input().split())
if n==1 and k==1:
    print(1)
    exit()
if k==1:
    print(0)
    exit()
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
mod=10**9+7
pk2=[0]*(k-1)
pk2[0]=1
for i in range(k-2):
    pk2[i+1]=pk2[i]*(k-2-i)%mod
def p(n,r):
    if n<r:
        return 0
    return pk2[r]
ans=k
q=[0]
v=[0]*n
v[0]=1
while len(q)>0:
    s=q.pop(0)
    c=0
    for es in g[s]:
        if v[es]==0:
            v[es]=1
            c+=1
            q.append(es)
    if s==0:
        if k-1<c:
            ans=0
            break
        for i in range(k-c,k):
            ans*=i
            ans%=mod
        ans%=mod
    else:
        ans*=p(k-2,c)
        ans%=mod
print(ans%mod)


### FIXED CODE ###

from collections import deque
n,k=map(int,input().split())
if n==1 and k==1:
    print(1)
    exit()
if k==1:
    print(0)
    exit()
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)
mod=10**9+7
ans=k
q=deque([0])
v=[0]*n
v[0]=1
vc=1
while q and vc<n:
    s=q.popleft()
    c=0
    if s==0:
        kai=k-1
    else:
        kai=k-2
    for es in g[s]:
        if v[es]==0:
            v[es]=1
            vc+=1
            c+=1
            q.append(es)
            ans*=kai
            ans%=mod
            kai-=1
print(ans%mod)