Harryxun/stf_run huggingface dataset:
n=int(input())
x=input()
if bin(x).count("1")==0:
  for i in x:
    print(1)
else:
  	print(0)

### FIXED CODE ###

n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i==n-1: print(2)
        elif x[i]=="0": print(1)
        else: print(0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)
h, w, k = map(int, input().split())
s = [""] * h
for i in range(h):
    s[i] = input()

ans = [[0 for i in range(w)] for j in range(h)]
lcnt = [0] * h
cnt = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            lcnt[i] += 1

flag = 0
mem = [0] * w

a = 1

for i in range(h):
    t = 0
    j = 0

    while t < lcnt[i]:

        if s[i][j] == "#":
            t += 1
            ans[i][j] = a
            a += 1
        else:
            ans[i][j] = a

        j += 1

    for l in range(j, w):
        ans[i][l] = a - 1

for i in range(h):
    if lcnt[i] > 0:
        for j in range(w):
            mem[j] = ans[i][j]
        break

t = 0
while lcnt[t] == 0:
    for i in range(w):
        ans[t][i] = mem[i]
    lcnt[i] = 1
    t += 1

for i in range(1, h):
    if lcnt[i] == 0:
        for j in range(w):
            ans[i][j] = ans[i - 1][j]

for i in range(h):
    for j in range(w):
        print(ans[i][j], end="")
        if j != w - 1:
            print(" ", end="")
    print()

### FIXED CODE ###

h, w, k = map(int, input().split())
s = [""] * h
for i in range(h):
    s[i] = input()

ans = [[0 for i in range(w)] for j in range(h)]
lcnt = [0] * h
cnt = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            lcnt[i] += 1

flag = 0
mem = [0] * w

a = 1

for i in range(h):
    t = 0
    j = 0

    while t < lcnt[i]:

        if s[i][j] == "#":
            t += 1
            ans[i][j] = a
            a += 1
        else:
            ans[i][j] = a

        j += 1

    for l in range(j, w):
        ans[i][l] = a - 1

for i in range(h):
    if lcnt[i] > 0:
        for j in range(w):
            mem[j] = ans[i][j]
        break

t = 0
while lcnt[t] == 0:
    for i in range(w):
        ans[t][i] = mem[i]
    lcnt[t] = 1
    t += 1

for i in range(1, h):
    if lcnt[i] == 0:
        for j in range(w):
            ans[i][j] = ans[i - 1][j]

for i in range(h):
    for j in range(w):
        print(ans[i][j], end="")
        if j != w - 1:
            print(" ", end="")
    print()
n = int(input())
a = []
for i in range(n): 
    a.append( 1/int(input()))

print(1/sum(a))


### FIXED CODE ###

n = int(input())
a = [1/int(e) for e in input().split()]

print(1/sum(a))
N=int(input())
H=list(map(int,input().split()))
now=0
max=0
count=0
while now>len(N)-1:
  if H[now]>=H[now+1]:
    count+=1
    now+=1
  else:
    now+=1
    if count>max:
      max=count
    count=0
print(max)

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
now=0
max=0
count=0
while now<N-1:
  if H[now]>=H[now+1]:
    count+=1
    now+=1
  else:
    now+=1
    if count>max:
      max=count
    count=0
if count>max:
    max=count
print(max)
N,K = map(int,input().split())
A = list(map(int,input().split()))

from collections import deque 
tmp = 1
num = deque()
A_list = deque([[] for i in range(N+1)])
 
for i in range(N):
    num.append(tmp)
    A_list[tmp].append(i)
    if tmp == A[tmp-1]:
        judge = tmp
        flag1 = 1
        break
    tmp = A[tmp-1]
    if tmp in num:
        judge = tmp
        flag2 = 1
        break

if flag2 == 1:
    num_index = A_list[judge]
    print(num[(K-num_index[0])%(len(num)-num_index[0]) + num_index[0]])
elif flag1 == 1:
    if K > len(num):
        print(judge)
    else:
        print(num[K-1])

### FIXED CODE ###

N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))

from collections import deque 
tmp = 1
num = []
seen = [-1]*(N+1)
 
while seen[tmp] == -1:
    seen[tmp] = tmp
    num.append(tmp)
    tmp = A[tmp]


l = num.index(tmp)
c = len(num) - l

if K < l:
    print(num[K])
else:
    print(num[(K-l)%c+l])
import queue
N,M = map(int,input().split())
tree = [[] for _ in range(M+1)]
for i in range(M):
    a,b = map(int,input().split())
    tree[a].append([b,a])
    tree[b].append([a,b])

que = queue.Queue()
que.put(1)
result = [[-1,100000] for _ in range(N+1)]
result[1][1] = 0

while(True):
    if que.empty():
        break
    nex = que.get()
    
    for i in tree[nex]:
        if result[i[0]][0] == -1  :
            result[i[0]][0] = nex
            result[i[0]][1] = result[nex][1] +1

            
            que.put(i[0])

for i in range(2,N+1):
    for j in tree[i]:
        if result[j[0]][1] == result[i][1] -1:
            result[i][0] = j[0] 
result = result[2:]
if result.count(-1) !=0:
    print("No")
else :
    print("Yes")
    for i in result:
        print([i[0]])




### FIXED CODE ###

import queue
N,M = map(int,input().split())
tree = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

que = queue.Queue()
que.put(1)
result = [-1]*(N+1)
result[1] = 0
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        if result[i] == -1:
            result[i] = start
            que.put(i)

if -1 in result[2:]:
    print("No")
else:
    print("Yes")
    for i in result[2:]:
        print(i)
n,m=map(int,input().split())
sc=[list(map(int,input().split())) for i in range(m)]
for i in range(10**(n-1),10**n):
    stri=str(i+1)
    c=0
    for j in range(m):
        if stri[sc[j][0]-1]==str(sc[j][1]):
            c+=1
        else:
            continue
    if j==m-1 and c==m:
        print(i+1)
        break
    elif j==m-1 and i==10**n-1:
        print(-1)
        break

### FIXED CODE ###

n,m=map(int,input().split())
sc=[list(map(int,input().split())) for i in range(m)]

for i in range(10**n):
  i2=str(i)
  if len(i2)==n and all([i2[s-1]==str(c) for s,c in sc]):
      print(i2)
      exit()
print(-1)
A = [int(input()) for _ in range(5)]

y = min([x%10 for x in A if x%10])

print(sum([10*(x//10 + bool(x%10)) for x in A]) -10 + y)

### FIXED CODE ###

A = [int(input()) for _ in range(5)]
 
y = min([10] + [x%10 for x in A if x%10])
 
print(sum([10*(x//10 + bool(x%10)) for x in A]) -10 + y)
a= input()

if (a >= 1000):
    print ("ABD")
else:
    print("ABC")


### FIXED CODE ###

a= int(input())

if (a >= 1000):
    print ("ABD")
else:
    print("ABC")
# AOJ ITP1_8_C

def numinput():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a

def main():
    counts = []
    for i in range(26): counts.append(0)

    while True:
        string = input()
        if not len(string): break   # 長さが0のstringが来たら終了
        for k in range(len(string)):
            c = string[k]
            if 97 <= ord(c) <= 122:
                counts[ord(c) - 97] += 1
            elif 65 <= ord(c) <= 90:
                counts[ord(c) - 65] += 1

    # 結果を出力。
    for i in range(26):
        print(chr(97 + i) + " : " + str(counts[i]))

if __name__ == "__main__":
    main()


### FIXED CODE ###

# AOJ ITP1_8_C

import sys

def main():
    counts = []
    for i in range(26): counts.append(0)

    lines = sys.stdin.readlines()

    for i in range(len(lines)):
        string = lines[i]
        for k in range(len(string)):
            c = string[k]
            if 97 <= ord(c) <= 122:
                counts[ord(c) - 97] += 1
            elif 65 <= ord(c) <= 90:
                counts[ord(c) - 65] += 1

    # 結果を出力。
    for i in range(26):
        print(chr(97 + i) + " : " + str(counts[i]))

if __name__ == "__main__":
    main()

# Accepted.
N = int(input().split())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

count = 0
for i in range(N):
    if V[i] > C[i]:
        count += V[i] - C[i]

print (count)

### FIXED CODE ###

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

count = 0
for i in range(N):
    if V[i] > C[i]:
        count += V[i] - C[i]

print (count)
n = int(input())
nums = list(map(int, input().split()))

num_free = 0
num_color = [False] * 8
for rate in nums:
    if rate < 3200:
        num_color(rate // 400) = True
    else:
        num_free += 1

ans = sum(num_color)
print('{} {}'.format(ans, ans + num_free))


### FIXED CODE ###

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

num_free = 0
num_color = [False] * 8
for rate in nums:
    if rate < 3200:
        num_color[rate // 400] = True
    else:
        num_free += 1

ans = sum(num_color)
print('{} {}'.format(max(ans, 1), ans + num_free))
b = input()
 
if b = 'A':
    b = 'T'
elif b = 'T':
    b = 'A'
elif b = 'C':
    b = 'G'
else:
    b = 'C'
 
print(b)
b = input ')
if b = a


### FIXED CODE ###

b = input()

if b == 'A':
    b = 'T'
elif b == 'T':
    b = 'A'
elif b == 'C':
    b = 'G'
else:
    b = 'C'

print(b)
import sys, math
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    D = list(mi())
    ans = 1

    if D[0] != 0:
        print(0)
        return

    dic = defaultdict(int)
    for i in range(N):
        dic[D[i]] += 1

    for k, v in dic.items():
        if k == 0:
            continue
        ans *= pow(dic[k-1], v)

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys, math
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N = ii()
    D = list(mi())
    ans = 1

    if D[0] != 0:
        print(0)
        return

    dic = defaultdict(int)
    for i in range(N):
        dic[D[i]] += 1

    for i in range(1, N):
        ans *= dic[D[i]-1]
        ans %= 998244353

    print(ans)

if __name__ == '__main__':
    main()
n = int(input())
a,b,c = [0]*n, [0]*n, [0]*n
for i in range(n):
    a[i], b[i],c[i] = map(int,input().split())
dp = [[0]*3 for _ in range(n)]
dp[0] = [a[0],b[0],c[0]]
for i in range(n-1):
    dp[i+1][0] = max(dp[i+1][0], dp[i][1]+a[i+1], dp[i][2]+a[i+1])
    dp[i+1][1] = max(dp[i+1][1], dp[i][0]+b[i+1], dp[i][2]+b[i+1])
    dp[i+1][2] = max(dp[i+1][2], dp[i][0]+c[i+1], dp[i][1]+c[i+1])
print(max(dp[n-1]))

### FIXED CODE ###

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

dp = [float("inf") for _ in range(n)]
dp[0] = 0
for i in range(n-1):
    dp[i+1] = min(dp[i+1], dp[i]+abs(h[i+1]-h[i]))
    if i<n-2:
        dp[i+2] = min(dp[i+2], dp[i]+abs(h[i+2]-h[i]))
print(dp[n-1])
n = int(input())

divisors =[]
for i in range(1,int(n/2)+1):
    if n%i == 0:
        divisors.append(i)
divisors.append(n)
print(divisors)
x=len(divisors)
print(x)
gojyu=[]
for j in range(x-1):
    for k in range(x-1):
        if divisors[j]*divisors[k] == n:
            gojyu.append(divisors[j]+divisors[k]-2)
print(min(gojyu))


### FIXED CODE ###

n = int(input())
divisors =[]
for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        divisors.append(i)
gojyu=[]
for j in divisors:
    kyori = j + n/j - 2
    gojyu.append(int(kyori))
print(min(gojyu))
import numpy as np

W,H,N = map(int,input().split())
l = np.zeros((H,W)) #	要素0のH×W配列

for i in range(N):
  x,y,a = map(int,input().split())

  if a==1:
    l[:,:x] = 1
    #print(l[:,x:])
  elif a==2:
    l[:,x:] = 1
  elif a==3:
    l[:y,:] = 1
  elif a==4:
    l[y:,:] = 1
#print(H*W-int(l.sum().sum()))
print(H*W-int(l.sum()))

### FIXED CODE ###

import numpy as np

W,H,N = map(int,input().split())
l = np.zeros((H,W)) #	要素0のH×W配列

for i in range(N):
  x,y,a = map(int,input().split())

  if a==1:
    l[:,:x] = 1
    #print(l[:,x:])
  elif a==2:
    l[:,x:] = 1
  elif a==3:
    l[:y,:] = 1
  elif a==4:
    l[y:,:] = 1
#print(H*W-int(l.sum().sum()))
print(H*W-int(l.sum()))
a,b,c=[int(x) for x in input().split()]
if c<=a or c<=b: print("No")
else if 2(a*b+b*c+c*a)<a**2+b**2+c**2: print("Yes")
else: print("No")

### FIXED CODE ###

a,b,c=[int(x) for x in input().split()]
if c<=a or c<=b: print("No")
elif 2*(a*b+b*c+c*a)<a**2+b**2+c**2: print("Yes")
else: print("No")
a = input()
if a = A:
  print(T)
elif a = T:
  print(A)
elif a = G:
  print(C)
else:
  print(G)


### FIXED CODE ###

a = input()
if a == "A":
  print("T")
elif a == "T":
  print("A")
elif a == "G":
  print("C")
else:
  print("G")
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for a in range(A+1):
  for b in range(B+1):
    
  	for c in range(C+1):
      value = 500*a + 100*b + 50*c 
      if value == X:
      	ans += 1
print(ans)

### FIXED CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for a in range(A+1):
  for b in range(B+1):
    for c in range(C+1):
      value = 500*a + 100*b + 50*c 
      if value == X:
      	ans += 1
print(ans)
a = int(input())
b = int(input())

import math

c=a*(10**int (math.log10(b) + 1))+b

if int(math.sqrt(c)) == math.sqrt(c):
    print("Yes")
    print(c)
else:
    print("No")
    print(c)

### FIXED CODE ###

from math import sqrt
a, b = input().split()
n = int(a+b)
if(int(sqrt(n))**2 == n):
    print("Yes")
else:
    print("No")
N = int(input())
lst = [0] * 9

for x in [int(x) for x in input().split()]:
    if x <= 399:
        lst[0] = 1
    elif x <= 799:
        lst[1] = 1
    elif x <= 1199:
        lst[2] = 1
    elif x <= 1599:
        lst[3] = 1
    elif x <= 1999:
        lst[4] = 1
    elif x <= 2399:
        lst[5] = 1
    elif x <= 2799:
        lst[6] = 1
    elif x <= 3199:
        lst[7] = 1
    else:
        lst[8] += 1

a = sum(lst[:-1])
b = lst[8]
if a == 0 and b > 0:
    print("1 {0}".format(b))
else:
    print("{0} {1}".format(a, a + b))


### FIXED CODE ###

n = int(input().replace(' ', ''))
if n % 4 == 0:
    print('YES')
else:
    print('NO')
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

a,b,c,d = input().split(' ')

a = int(a)
b = int(b)
c = int(c)
d = int(d)

saisyo_kobaisu = lcm(c, d)

counter = 0

counter = counter + ((b // c) + (b // d) - (b // saisyo_kobaisu))
counter = counter - (((a - 1) // c) + ((a - 1) // d) - ((a - 1) // saisyo_kobaisu))

print(b - a + 1 - counter)


### FIXED CODE ###

# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

a,b,c,d = input().split(' ')

a = int(a)
b = int(b)
c = int(c)
d = int(d)

hoge = lcm(c,d)

counter = 0

counter = counter + ((b // c) + (b // d) - (b // hoge))
counter = counter - (((a - 1) // c) + ((a - 1) // d) - ((a - 1) // hoge))

print(b - a + 1 - counter)
n,m= map(int,input().split())
cnt=0
acc=0
ac=[0]*n
for i in range(m):
	p,s= map(str,input().split())
	if ac[int(p)]==0:
		if s=='AC':
			acc+=1
			ac[int(p)]=1
		else:
			cnt+=1
print(acc,cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n,m=map(int,input().split())
    w=[0]*(n+1)
    a=[0]*(n+1)
    for i in range(m):
        p,s=map(str,input().split())
        p=int(p)
        if a[p]==0:
            if s=='WA':
                w[p]+=1
            else:
                a[p]=1
    wa=0
    for i in range(1,n+1):
        wa=wa+a[i]*w[i]
    print(sum(a),wa)

if __name__ == '__main__':
    main()
a,b = input().split()

if a+b >= 10:
    print("error")
else:
    print(a+b)

### FIXED CODE ###

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

if a+b >= 10:
    print("error")
else:
    print(a+b)
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
RLI = []
for i in range(n):
  l, r = map(int, input().split())
  RLI.append(r*U*U + l*U + i)
RLI.sort()
B = [0]*(n+1)
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for rli in RLI:
  rl, i = divmod(rli, U)
  r, l = divmod(rl, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

### FIXED CODE ###

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")
a = int(input())
b = int(input())/2
print(a+b)

### FIXED CODE ###

a, b = map(int, input().split())
print(int(a + b/2))
a = int(input())
b = int(input())
if (a*b)%2==0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b)%2==0:
  print("Even")
else:
  print("Odd")
s = map(str,input())
print(s.replace(","," "))

### FIXED CODE ###

s = str(input())
print(s.replace(","," "))
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a+=list(map(int, input().split()))
n = len(a)
q = int(input())
max_dbl_line = 6

def dist(i, j):
    dw = abs(i%w - j%w)
    dh = abs(i//w - j//w)
    return dw + dh

idx_table = [0] * n
for i in range(n):
    idx_table[a[i]-1] = i

# ダブンリングテーブル作成
dbl = [[0] * n for i in range(max_dbl_line)]
tmp = []
for i in range(n):
    if a[i]+d in a:
        next_node = idx_table[i]
    else:
        next_node = -1
    if next_node!=-1:
        next_d = dist(idx_table[i], next_node)
    else:
        next_d = float('inf')
    tmp.append((next_node, next_d))
dbl[0] = tmp
for i in range(max_dbl_line-1):
    temp = []
    for j in range(n):
        next_node = dbl[i][dbl[i][j][0]][0]
        next_d = dbl[i][j][1]+dbl[i][dbl[i][j][0]][1]
        temp.append((next_node, next_d))
    dbl[i+1] = temp

def f(l, r):
    cnt = (r-l)//d
    ret = 0
    now = idx_table[i]
    if cnt==0:
        return ret
    for i in range(max_dbl_line):
        if cnt & 1<<i:
            ret+=dbl[i][now][1]
            now = now + d*2**i
    return ret

for i in range(q):
    l, r = map(int, input().split())
    print(f(l,r))

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, d = map(int, input().split())
n = h*w
a = [0]*n
for i in range(h):
    t = list(map(int, input().split()))
    for j in range(w):
        a[w*i+j] = t[j]-1

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [0] * n
for i in range(n):
    idx_list[a[i]] = i

dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    l-=1; r-=1
    print(dist_list[r] - dist_list[l])
s=input()
if s=="Sunny":
    print("Cloudy ")　
if s=="Cloudy":
    print("Rainy")
if s=="Rainy":
    print("Sunny")


### FIXED CODE ###

S=input()
if S == "Sunny":
    print("Cloudy")
if S == "Cloudy":
    print("Rainy")
if S == "Rainy":
    print("Sunny")
n=int(input())
a=list(map(int, input().split()))
count=0
for i in range(len(a)):
    if a[i]==i+1:
        a[i],a[i+1]=a[i+1],a[i]
        count+=1
print(count)

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
count=0
if a[-1]==len(a):
    a[-1],a[-2]=a[-2],a[-1]
    count+=1
    
for i in range(len(a)):
    if a[i]==i+1:
        a[i],a[i+1]=a[i+1],a[i]
        count+=1
print(count)
import sys
input = sys.stdin.buffer.readline
from collections import deque
from scipy.special import perm

def main():
    N,K = map(int,input().split())
    tree = [[] for _ in range(N)]
    INF = 10**9+7
    for _ in range(N-1):
        a,b = map(int,input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
        
    q = deque()
    go = [True for _ in range(N)]
    go[0] = False
    for i in tree[0]:
        go[i] = False
    ans = K*perm(K-1,len(tree[0]),exact = True)
    for i in tree[0]:
        q.append(i)
        while q:
            now = q.popleft()
            count = 0
            for fol in tree[now]:
                if go[fol]:
                    count += 1
                    q.append(fol)
                    go[fol] = False
            u = perm(K-2,count,exact = True)
            ans *= u
            ans %= INF
    
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import copy
from collections import deque

def main():
    N,K = map(int,input().split())
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    go = [False for _ in range(N)]
    go[0] = True
    for num in edge[0]:
        go[num] = True
    MOD = 10**9+7
    fac = [0 for _ in range(K+1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,K+1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def per(x,y):
        num = ((fac[x]*invfac[x-y])%MOD)
        return num

    if K-1 < len(edge[0]):
        print(0)
        exit()
    ans = K*(per(K-1,len(edge[0])))

    q = deque(edge[0])
    while q:
        now = q.popleft()
        use = 0
        for fol in edge[now]:
            if not go[fol]:
                use += 1
                go[fol] = True
                q.append(fol)
        if use > K-2:
            print(0)
            exit()
        num = per(K-2,use)
        ans *= num
        ans %= MOD
        
    print(ans%MOD)

if __name__ == "__main__":
    main()
N = int(input())
S = input()

rslt = [S[0]]
S = [i for i in S[1:]]

for i in S:
    if rslt[-1] != i:
        rslt.extend(i)

len(rslt)'abcd'[-1]

### FIXED CODE ###

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

rslt = [S[0]]
S = [i for i in S[1:]]

for i in S:
    if rslt[-1] != i:
        rslt.extend(i)

print(len(rslt))
S = input()
T = input()
r = 0
for i in range(3):
	if S[i] == T[i]:
    	r += 1
print(r)

### FIXED CODE ###

S = input()
T = input()
r = 0
for i in range(3):
    if S[i] == T[i]:
        r += 1
print(r)
v=[int(input()) for_ in range(6)]
print('Yay!' if all([abs(v[i]-v[i+1])<=v[5] for i in range(4)) else ':(')

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if e-a <= k:
    print('Yay!')
else:
    print(':(')
import sys
A, B = map(int,input().split())
amin, amax = A / 0.08, (A + 1) / 0.08
bmin, bmax = B / 0.10, (B + 1) / 0.10

if amax <= bmin or bmax <= amin:#解なし：区間重なりなし
    print(-1)
    sys.exit()

ans = np.ceil(max(amin, bmin)).astype(int)

if ans >= amax or ans >= bmax:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
import numpy as np
A, B = map(int,input().split())
amin, amax = A / 0.08, (A + 1) / 0.08
bmin, bmax = B / 0.10, (B + 1) / 0.10

if amax <= bmin or bmax <= amin:#解なし：区間重なりなし
    print(-1)
    sys.exit()

ans = np.ceil(max(amin, bmin)).astype(int)

if ans >= amax or ans >= bmax:
    print(-1)
else:
    print(ans)