Harryxun/stf_run huggingface dataset:
import math
n=int(input())
a=[int(i) for i in input().split()]

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : math.gcd(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
    
tree = SegmentTree(n)
for i in range(n):
    tree.update(i,a[i])

max_=tree.query(1,n+1)
for i in range(1,n-1):
    max_=max(max_,math.gcd(tree.query(0,i+1),tree.query(i+1,n+1)))
max_=max(max_,tree.query(0,n))
print(max_)

### FIXED CODE ###

import fractions
n=int(input())
a=[int(i) for i in input().split()]

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : fractions.gcd(x,y), default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
    
tree = SegmentTree(n)
for i in range(n):
    tree.update(i,a[i])

max_=tree.query(1,n)
for i in range(1,n-1):
    max_=max(max_,fractions.gcd(tree.query(0,i),tree.query(i+1,n)))
max_=max(max_,tree.query(0,n-1))
print(max_)
n = int(input())
a = list(map(int, input().split()))
cnt = 0
i = 0
while i < len(a):
    while a[i] != i + 1:
        cnt += 1
        a.pop(i)
        if len(a) == 0:
            break
    i += 1
if a == []:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
cnt = 0
i = 0
j = 0
f_flg = 0
while i < len(a) and j < len(a):
    while a[j] != i + 1:
        cnt += 1
        j += 1
#         print(j)
        if j > len(a) - 1:
            if f_flg == 0:
                print(-1)
                exit()
            break
    f_flg = 1
    i += 1
    j += 1

print(cnt)
N,M = list(map(int,input().split()))
p = []
for i in range(M):
    x,y = list(map(str, input().split()))
    p.append([int(x),y])
count = [[0,0]for i in range(M)]
ansac = 0
answa = 0
for i in range(M):
    if count[p[i][0]-1][1] != 0:
        pass
    else:
        if p[i][1] == 'AC':
            count[p[i][0]-1][1] += 1
        else:
            count[p[i][0]-1][0] += 1
for i in range(N):
    answa += count[i][0]
    ansac += count[i][1]
print(str(ansac) + ' ' + str(answa))

### FIXED CODE ###

N,M = list(map(int,input().split()))
p = []
for i in range(M):
    x,y = list(map(str, input().split()))
    p.append([int(x),y])
count = [[0,0]for i in range(N)]
ansac = 0
answa = 0
for i in range(M):
    if count[p[i][0]-1][1] != 0:
        pass
    else:
        if p[i][1] == 'AC':
            count[p[i][0]-1][1] += 1
        else:
            count[p[i][0]-1][0] += 1
for i in range(N):
    if count[i][1] > 0:
        answa += count[i][0]
    ansac += count[i][1]
print(str(ansac) + ' ' + str(answa))
x = int(input())
a = 1
for i in x:
            if i == 0:
                      break
            print("Case {}: {}".format(a,i))
            a += 1

### FIXED CODE ###

import sys
a = 1

for i in sys.stdin:
        x = i.strip()
        if x == "0":
                break;
        print("Case {0}: {1}".format(a,x))
        a += 1
Copy
Copy
A, B = map(int, input().split())
 
if A <= 8 and B <= 8:
  print('Yay!')
else:
  print(':(')

### FIXED CODE ###

A, B = map(int, input().split())
 
if A <= 8 and B <= 8:
  print('Yay!')
else:
  print(':(')
t,x=int(input().split())
print(t/x)

### FIXED CODE ###

t,x=map(int,input().split())
print(t/x)
import sys
sys.setrecursionlimit(10**6)
N = int(input())
li = [[int(x) for x in input().split()] for _ in range(N)]
map = [[-1 for _ in range(101)] for _ in range(101)]
ans = [0]*3
for i in range(101):
    for j in range(101):
        h = -1
        flag = True
        for x in li:
            if(h == -1):
                h=x[2]+abs(x[0]-i)+abs(x[1]-j)
            else:
                if(h!=x[2]+abs(x[0]-i)+abs(x[1]-j)):
                    flag = False
        if(flag):
            ans=[str(i),str(j),str(h)]
            break
print(ans[0]+' '+ans[1]+' '+ans[2])


### FIXED CODE ###

import sys
from operator import itemgetter
sys.setrecursionlimit(10**7)
N = int(input())
li = [[int(x) for x in input().split()] for _ in range(N)]
li.sort(key=itemgetter(2),reverse=True)
map = [[-1 for _ in range(101)] for _ in range(101)]
ans = [0]*3
for i in range(101):
    for j in range(101):
        h = -1
        flag = True
        for x in li:
            if(h == -1):
                h=x[2]+abs(x[0]-i)+abs(x[1]-j)
            else:
                if(x[2]!=0):
                    if(h!=x[2]+abs(x[0]-i)+abs(x[1]-j)):
                        flag = False
                else:
                    if(h>abs(x[0]-i)+abs(x[1]-j)):
                        flag = False
        if(flag):
            if(h>ans[2]):
                ans=[i,j,h]

print(str(ans[0])+' '+str(ans[1])+' '+str(ans[2]))
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
num = 0
for i in A:
    num += i
if A[M] >= num//4*M:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort(reverse = True)
num = 0
for i in A:
    num += i
if A[M-1] >= num/(4*M):
    print('Yes')
else:
    print('No')
N = int(input())
an = list(map(int,input().split()))

c = 1
cp = 0

for i in N:
  ai = an[i]
  if ai != c:
    cp += 1
    
  elif ai == c:
    c += 1
    
print(cp)

### FIXED CODE ###

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

c = 1
cp = 0

for i in range(N):
  ai = an[i]
  if ai != c:
    cp += 1
    
  elif ai == c:
    c += 1
    
if N == cp:
    cp = -1

print(cp)
s = input()
K = int(input())
result = []
alphabet = list("abcdefghijklmnopqrstuvwxyz")

for u in alphabet:
    for i in range(len(s)):
        if s[i] == u:
            for j in range(len(s) - i):
                result.append(s[i:i + j + 1])
    if len(result) > K:
        break
result = list(set(result))
result.sort()
print(result[K - 1])


### FIXED CODE ###

s = input()
K = int(input())
subs = []
for i in range(0, len(s)):
    for j in range(i + 1, K + i + 1 if i + K <= len(s) else len(s) + 1):
        subs.append(s[i:j])


subs = list(set(subs))

subs.sort()
print(subs[K - 1])
from math import gcd
from bisect import bisect_left, bisect_right

MOD = 10 ** 9 + 7
pow2 = [1] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
	pow2[i] = (pow2[i - 1] * 2) % MOD

N = int(input())

iwasies = []
for i in range(N):
	A, B = map(int, input().split())
	if A == 0 and B == 0:
		continue
	elif A == 0:
		iwasies.append((0, 1))
	elif B == 0:
		iwasies.append((1, 0))
	else:
		g = gcd(A, B)
		A //= g
		B //= g
		if A < 0:
			iwasies.append((-A, -B))
		else:
			iwasies.append((A, B))

iwasies.sort()
badpairs = set()
for i in range(N):
	A, B = iwasies[i]
	abcount = bisect_right(iwasies, (A, B)) - bisect_left(iwasies, (A, B))
	
	Ao, Bo = B, -A
	if Ao < 0:
		Ao, Bo = -Ao, -Bo
	
	aobocount = bisect_right(iwasies, (Ao, Bo)) - bisect_left(iwasies, (Ao, Bo))
	
	if aobocount > 0:
		if (A, B) < (Ao, Bo):
			badpairs.add(((A, B, abcount), (Ao, Bo, aobocount)))
		else:
			badpairs.add(((Ao, Bo, aobocount), (A, B, abcount)))

numiwasi = len(iwasies)
sociable = numiwasi
ans = 1

for bp in badpairs:
	count1 = bp[0][2]
	count2 = bp[1][2]
	sociable -= (count1 + count2)
	ans = (ans * (pow2[count1] + pow2[count2] - 1)) % MOD
ans = (ans * pow2[sociable]) % MOD

print(ans - 1)	

### FIXED CODE ###

from math import gcd
from bisect import bisect_left, bisect_right

MOD = 10 ** 9 + 7
pow2 = [1] * (2 * 10 ** 5 + 1)
for i in range(1, 2 * 10 ** 5 + 1):
	pow2[i] = (pow2[i - 1] * 2) % MOD

N = int(input())
zero = 0
iwasies = []
for i in range(N):
	A, B = map(int, input().split())
	if A == 0 and B == 0:
		zero += 1
	elif A == 0:
		iwasies.append((0, 1))
	elif B == 0:
		iwasies.append((1, 0))
	else:
		g = gcd(A, B)
		A //= g
		B //= g
		if A < 0:
			iwasies.append((-A, -B))
		else:
			iwasies.append((A, B))

numiwasi = len(iwasies)
iwasies.sort()
badpairs = set()
for i in range(numiwasi):
	A, B = iwasies[i]
	abcount = bisect_right(iwasies, (A, B)) - bisect_left(iwasies, (A, B))
	
	Ao, Bo = B, -A
	if Ao < 0:
		Ao, Bo = -Ao, -Bo
	
	aobocount = bisect_right(iwasies, (Ao, Bo)) - bisect_left(iwasies, (Ao, Bo))
	
	if aobocount > 0:
		if (A, B) < (Ao, Bo):
			badpairs.add(((A, B, abcount), (Ao, Bo, aobocount)))
		else:
			badpairs.add(((Ao, Bo, aobocount), (A, B, abcount)))

sociable = numiwasi
ans = 1

for bp in badpairs:
	count1 = bp[0][2]
	count2 = bp[1][2]
	sociable -= (count1 + count2)
	ans = (ans * (pow2[count1] + pow2[count2] - 1)) % MOD
ans = (ans * pow2[sociable]) % MOD

print((ans + zero - 1) % MOD)
N, L = map(int, input().split())
S = [input() for i in range(L)]
S.sort()
ans = ""
for i in S:
    ans += i
print(ans)

### FIXED CODE ###

n,l = map(int,input().split())
A = [input() for _ in range(n)]
A.sort()
ans = ''
for i in range(n):
    ans += A[i]
 
print(ans)
a=input()
if a="ABC":
  print("ARC")
else:
  print("ABC")

### FIXED CODE ###

n=input()

if (n =="ABC"):
    print("ARC")
else:
    print("ABC")
N = input()
l = len(N)
n = N[l]
if n == "2" or '4' or '5' or '7' or '9':
  print("hon")
elif n == '0' or '1' or '6' or '8':
  print('pon')
else:
  print('bon')

### FIXED CODE ###

N = input()
n = N[len(N)-1]
if n == "2" or n== '4' or n=='5' or n=='7' or n=='9':
  print("hon")
elif n == '0' or n=='1' or n=='6' or n=='8':
  print('pon')
else:
  print('bon')
from collections import defaultdict
def solve():
    N = int(input())
    G = defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        G[u].append((v,w))
        G[v].append((u,w))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
def solve():
    N = int(input())
    G = defaultdict(list)
    for i in range(N-1):
        u,v,w = map(int,input().split())
        u -= 1
        v -= 1
        G[u].append((v,w))
        G[v].append((u,w))

    res = [0] * N

    dfs(0,-1,1,G,res)

    print(*res, sep='\n')
def dfs(v,p,c,G,res):
    res[v] = c
    for e in G[v]:
        if e[0] == p:
            continue
        if e[1] % 2 != 0:
            dfs(e[0], v, 1-c,G,res)
        else:
            dfs(e[0],v,c,G,res)
        
if __name__ == '__main__':
    solve()
n = int(input())
a = list(map(int, input().split()))
m = []
for i in range(n - 2):
    if a[i] < a[i + 1] < a[i + 2] or a[i + 2] < a[i + 1] < a[i]:
        m.append(0)
    if a[i + 1] < a[i] < a[i + 2] or a[i + 1] < a[i + 2] < a[i]:
        m.append(1)
    if a[i] < a[i + 2] < a[i + 1] or a[i + 2] < a[i] < a[i + 1]:
        m.append(-1)

s = sum(abs(a[i] - a[i + 1]) for i in range(n - 1))

print(s - abs(a[0] - a[1]))
for i, m0 in enumerate(m):
    if m0 == 0:
        print(s)
    elif m0 > 0:
        print(s - 2 * abs(a[i + 1] - a[i + 2]))
    elif m0 < 0:
        print(s - 2 * abs(a[i + 2] - a[i + 3]))
print(s - abs(a[n - 1] - a[n]))


### FIXED CODE ###

n = int(input())
a = [0] + list(map(int, input().split())) + [0]
m = []
for i in range(n):
    if a[i] <= a[i + 1] <= a[i + 2] or a[i + 2] <= a[i + 1] <= a[i]:
        m.append(0)
    elif a[i] <= a[i + 2] <= a[i + 1] or a[i + 1] <= a[i + 2] <= a[i]:
        m.append(1)
    elif a[i + 1] <= a[i] <= a[i + 2] or a[i + 2] <= a[i] <= a[i + 1]:
        m.append(-1)

s = sum(abs(a[i] - a[i + 1]) for i in range(n + 1))

for i, m0 in enumerate(m):
    if m0 == 0:
        print(s)
    elif m0 == 1:
        print(s - 2 * abs(a[i + 1] - a[i + 2]))
    elif m0 == -1:
        print(s - 2 * abs(a[i] - a[i + 1]))
N, M = map(int, input().split())
S = input()
T = input()

from collections import gcd

def solve(N,M,S,T):
    g = gcd(N,M)
    for i in range(g):
        if S[N//g*i]!=T[M//g*i]:
            return -1
    ans = N*M//g
    return ans
print(solve(N,M,S,T))

### FIXED CODE ###

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

from fractions import gcd

def solve(N,M,S,T):
    g = gcd(N,M)
    for i in range(g):
        if S[N//g*i]!=T[M//g*i]:
            return -1
    ans = N*M//g
    return ans
print(solve(N,M,S,T))
n = int(input())
li = [sorted(list(input())) for a in range(n)]
ans = 0
le = len(li)
while le != 1:
  t = li[0]
  cnt = 0
  for n, w in reversed(list(enumerate(li[1:]))):
    if t == w:
      cnt += 1
      li.pop(n + 1)
  ans += cnt * (cnt + 1) / 2
  li.pop(0)
  le = len(li)

print(ans)

### FIXED CODE ###

n = int(input())
li = [''.join(sorted(input())) for _ in range(n)]

ans = 0
w_dic = {}
for l in li:
  if not w_dic.get(l):
    w_dic[l] = 1
  else:
    ans += w_dic[l]
    w_dic[l] = w_dic[l] + 1

print(int(ans))
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=1
mod=10**9+7
if N%2==0:
    for k in range(N//2):
        if A[2*k]==2*k+1 and A[2*k+1]==2*k+1:
            ans=ans*2%mod
            continue
        else:
            ans=0
            break
if N%2==1:
    if A[0]==0:
        ans=2
        for k in range(N//2-1):
            if A[2*k+2]==2*k+2 and A[2*k+1]==2*k+2:
                ans=ans*2%mod
                continue
            else:
                ans=0
                break
    else:
        ans=0
if N==1:
    if A[0]==0:
        ans=1
    else:
        ans=0
print(ans)

### FIXED CODE ###

A,op,B=map(str,input().split())
A=int(A)
B=int(B)
if op=="+":
    print(A+B)
else:
    print(A-B)
n = int(input())
path = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
parent = [-1]*n
size = [1]*n
d = [0]*n
def dfs(now):
    for nxt in path[now]:
        if nxt != parent[now]:
            parent[nxt] = now
            d[nxt] = d[now] + 1
            size[now] += dfs(nxt)
    return size[now]
dfs(0)
cnt = 0
now = n-1
for i in range((d[n-1]+1)//2 - 1):
    now = parent[now]
if size[now] >= n - size[now]:
    print('Snuke')
else:
    print('Fennec')


### FIXED CODE ###

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

n = int(input())
path = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
parent = [-1]*n
size = [1]*n
d = [0]*n
def dfs(now):
    for nxt in path[now]:
        if nxt != parent[now]:
            parent[nxt] = now
            d[nxt] = d[now] + 1
            size[now] += dfs(nxt)
    return size[now]
dfs(0)
cnt = 0
now = n-1
for i in range((d[n-1]+1)//2 - 1):
    now = parent[now]
if size[now] >= n - size[now]:
    print('Snuke')
else:
    print('Fennec')
a = int(a)
x = int(x)
x = a + a**2 + a**3
print(x)

### FIXED CODE ###

a = int(input())
x = a + a**2 + a**3
print(x)
import fractons
import functools

def lcm(n1, n2):
    return n1 * n2 // fractions.gcd(n1, n2)

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] //= 2

lcmA = functools.reduce(lcm, A)
gcdA = functools.reduce(fractions.gcd, A)
if (lcmA // gcdA) % 2 == 0:
    print(0)
else:
    print((M // lcmA + 1) // 2)

### FIXED CODE ###

import fractions
import functools

def lcm(n1, n2):
    return n1 * n2 // fractions.gcd(n1, n2)

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    A[i] //= 2

lcmA = functools.reduce(lcm, A)
gcdA = functools.reduce(fractions.gcd, A)
if (lcmA // gcdA) % 2 == 0:
    print(0)
else:
    print((M // lcmA + 1) // 2)
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def eprint(s):
    if type(s) != type('str'):
        s=str(s)

    sys.stderr.write(s+'\n')
    return

def main():
    s,t = input().split()
    a,b  = map(int, input().split())
    u = int(input())
    
    if u == s:
        print(a-1)
    else:
        print(b-1)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = sys.stdin.readline

def eprint(s):
    if type(s) != type('str'):
        s=str(s)

    sys.stderr.write(s+'\n')
    return

def main():
    s,t = input().split()
    a,b  = map(int, input().split())
    u = input().split('\n')[0]
    
    if s==u:
        print(a-1,b)
    else:
        print(a, b-1)

if __name__ == '__main__':
    main()
n,l=map(int,input().split())
ls=[]
for i in range(1,n+1):
  ls.append(abs(l-1+i))
mi=l.index(min(ls))
print(n*(l-1)+sum(range(1,n+1))-l-mi)

### FIXED CODE ###

n,l=map(int,input().split())
s=0
list=[]
for i in range(1,n+1):
  s+=i
  list.append(abs(l+i-1))
sum=n*(l-1)+s
m=list.index(min(list))
print(sum-l-m)
import math
n=int(input())
SN = 0
for i in range(1,math.ceil(math.log(n,10))+1):
  SN = SN + math.floor(n%(10**i)/(10**(i-1)))
if n%SN==0:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

S=str(input())
total = 0
for i in range(len(S)):
  total = total + int(S[i])
if int(S)%total==0:
  print('Yes')
else:
  print('No')
N = int(input())
V = list(map(int, input().split())
C = list(map(int, input().split())

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


### FIXED CODE ###

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

s = 0
for i in range(N):
	if V[i] >= C[i]:
		s += V[i]-C[i]
	else:
		s += 0
print(s)
n = int(input())
li = []

for _ in range(n):
    s = input()
    count = 0
    while True:
        if count + 1 >= len(s):
            break
        if s[count] == '(' and s[count+1] == ')':
            s = s[:count] + s[count+2:]
            count = max(0, count-1)
        else:
            count += 1
    li.append(s)

li2 = []
for i in li:
    count = 0
    for j in range(len(i)):
        if i[j] == ')':
            count += 1
        else:
            break
    li2.append((len(i) - count, count))

now = [0,0]
for l,r in li2:
    if l == 0 and r == 0:
        pass
    elif r == 0:
        if now[1] == 0:
            now[0] += l
        elif 0 < now[1] <= l:
            now[0] += l - now[1]
            now[1] = 0
        else:
            now[1] -= l
    elif l == 0:
        if now[0] == 0:
            now[1] += r
        elif 0 < now[0] <= r:
            now[1] += r - now[0]
            now[0] = 0
        else:
            now[0] -= r
    else:
        if min(now[0], l) > min(now[1], r):
            if now[0] > l:
                now[0] -= l
            else:
                now[1] += l - now[0]
                now[0] = 0
        else:
            if now[1] > r:
                now[1] -= r
            else:
                now[0] += r - now[1]
                now[1] = 0

if now[0] == 0 and now[1] == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = input()
t = input()

print('Yes' if s == t[:-1] else 'No')
# https://atcoder.jp/contests/abc133/tasks/abc133_e

# あー解説あたまいい
# そのノードで塗れる色の候補を持つのではなくて、
# そのノードの子で塗れる通りの数を持っておく
# あるノードの子で塗れる通りの数は、親とそのノードで塗る色の通りも確定してると考えると、(K-2)P(子の数)となる。(自身が根のときは自身の色の通りも考慮して、(K)P(子の数+1)となる)
# これをdfsで実装すれば良い

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    assert n >= r
    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  # 現在のuと親のp
    if len(tree[u]) == 1 and tree[u][0] == p:
        # 葉なので終了
        return 1
    ret = 1  # その地点までの通りの数
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print(dfs(0, -1))


### FIXED CODE ###

# https://atcoder.jp/contests/abc133/tasks/abc133_e

# あー解説あたまいい
# そのノードで塗れる色の候補を持つのではなくて、
# そのノードの子で塗れる通りの数を持っておく
# あるノードの子で塗れる通りの数は、親とそのノードで塗る色の通りも確定してると考えると、(K-2)P(子の数)となる。(自身が根のときは自身の色の通りも考慮して、(K)P(子の数+1)となる)
# これをdfsで実装すれば良い

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


MOD = 10**9 + 7

N, K = read_ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = read_ints()
    a, b = mina(a, b)
    tree[a].append(b)
    tree[b].append(a)


def perm_mod(n, r, mod=MOD):
    # assert n >= r
    ret = 1
    for _ in range(r):
        ret *= n
        ret %= mod
        n -= 1
    return ret


def dfs(u, p):  # 現在のuと親のp
    if len(tree[u]) == 1 and tree[u][0] == p:
        # 葉なので終了
        return 1
    ret = 1  # その地点までの通りの数
    for to in tree[u]:
        if to == p:
            continue
        ret *= dfs(to, u)
        ret %= MOD
    if p == -1:
        ret *= perm_mod(K, len(tree[u]) + 1)
    else:
        ret *= perm_mod(K - 2, len(tree[u]) - 1)

    return ret % MOD


print(dfs(0, -1))
N, K = map(int, input().split(''))
friends = list(map(int, input().split('')))

n = len([1 for x in friends if x>K])

print(n)

### FIXED CODE ###

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


n = len([1 for x in friends if x>=K])

print(n)
n=int(input())
d=dict()
for i in range(200):
    for j in range(i,200):
        d[i**5-j**5]=(i,j)
        d[i**5+j**5]=(i,-j)
a,b=d[n]
print(a,b)

### FIXED CODE ###

n=int(input())
d=dict()
for i in range(300):
    for j in range(300):
        d[i**5-j**5]=(i,j)
        d[i**5+j**5]=(i,-j)
a,b=d[n]
print(a,b)
s=input()
l=list("AKIHABARA".split("A"))[1:-1]

for ii in range(2**4):
  p="A" if ii%2 else ""
  i=ii
   for j in range(3):
    p+=l[j]
    i//=2
    p+="A" if i%2 else ""
  if s==p:print("YES");exit()
print("NO")

### FIXED CODE ###

s=input()
l=list("AKIHABARA".split("A"))[1:-1]

for ii in range(2**4):
  p="A" if ii%2 else ""
  i=ii
  for j in range(3):
    p+=l[j]
    i//=2
    p+="A" if i%2 else ""
  if s==p:print("YES");exit()
print("NO")
s = input()
m = "gp"*(len(s)//2+1)
g = 0
for i in range(s):
  if s[i] == m[i]:
    continue
  elif s[i] == "p":
    g -= 1
  else:
    g += 1
print(g)

### FIXED CODE ###

s = input()
m = "gp"*(len(s)//2+1)
g = 0
for i in range(len(s)):
  if s[i] == m[i]:
    continue
  elif s[i] == "p":
    g -= 1
  else:
    g += 1
print(g)