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

n=int(input())
A=list(map(int,input().split()))
idx=dict()
mod=10**9+7
for i in range(1+n):
    if A[i] in idx:
        x=idx[A[i]]
        y=i
        break
    idx[A[i]]=i
gawa=n-1-(y-x-1)
zentai=n-1
gawa_conb=[1]
for i in range(1,1+gawa):
    if i<1+gawa//2:
        gawa_conb.append(gawa_conb[-1]*(gawa-i+1)//i)
    else:
        gawa_conb.append(gawa_conb[gawa-i])
gawa_conb+=[0]*(zentai-gawa)
zentai_conb=[1]
for i in range(1,1+zentai):
    if i<1+zentai//2:
        zentai_conb.append(zentai_conb[-1]*(zentai-i+1)//i)
    else:
        zentai_conb.append((zentai_conb[zentai-i]))
if n>1:
    print((zentai_conb[1]+zentai_conb[0]*2-gawa_conb[0])%mod)
    for i in range(2,n):
        print((zentai_conb[i-2]+zentai_conb[i]+zentai_conb[i-1]*2-gawa_conb[i-1])%mod)
    print((zentai_conb[n-2]+zentai_conb[n-1]*2-gawa_conb[n-1])%mod)
    print((zentai_conb[n-1])%mod)
else:
    print(1)
    print(1)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
idx=dict()
mod=10**9+7
for i in range(1+n):
    if A[i] in idx:
        x=idx[A[i]]
        y=i
        break
    idx[A[i]]=i
kaijo=[1]
for i in range(1,n+2):
    kaijo.append((kaijo[-1]*i)%mod)
gyaku=[pow(kaijo[n+1],mod-2,mod)]
from collections import deque
gyaku=deque(gyaku)
for i in range(n+1,0,-1):
    gyaku.appendleft((gyaku[0]*i)%mod)
gawa=n-1-(y-x-1)
zentai=n-1
gawa_conb=[1]
for i in range(1,1+gawa):
    if i<1+gawa//2:
        gawa_conb.append((kaijo[gawa]*gyaku[i]*gyaku[gawa-i])%mod)
    else:
        gawa_conb.append(gawa_conb[gawa-i])
gawa_conb+=[0]*(zentai-gawa)
zentai_conb=[1]
for i in range(1,1+zentai):
    if i<1+zentai//2:
        zentai_conb.append((kaijo[zentai]*gyaku[i]*gyaku[zentai-i])%mod)
    else:
        zentai_conb.append((zentai_conb[zentai-i]))
if n>1:
    print((zentai_conb[1]+zentai_conb[0]*2-gawa_conb[0])%mod)
    for i in range(2,n):
        print((zentai_conb[i-2]+zentai_conb[i]+zentai_conb[i-1]*2-gawa_conb[i-1])%mod)
    print((zentai_conb[n-2]+zentai_conb[n-1]*2-gawa_conb[n-1])%mod)
    print((zentai_conb[n-1])%mod)
else:
    print(1)
    print(1)
### BUGGY CODE ###

n =int(input())

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

result = False

if n % 2 == 0:
    if len(a) == n and sum(a) == n*n/2:
        for i in range(n-1, -1, -2):
            if i not in set(a):break
        result = True

else:
    if len(a) == n and sum(a) == (n+1)*(n-1)/2:
        for i in range(n-1, -1, -2):
            if i not in set(a):break
        result = True
        
if result: print(2**int(n/2) % (10**9+7))
else:print(0)
  

### FIXED CODE ###

from  collections import Counter

n =int(input())

a = list(input().rstrip().split())

count_num = Counter(a)

result = True

if len(a) == n:
    if n % 2 == 0:
        for i in range(n-1, -1, -2):
            if count_num[str(i)] ==2:
                continue
            else:
                result = False
                break

    else:
        if count_num['0'] == 1:
            for i in range(n-1, 1, -2):                
                if count_num[str(i)] ==2:continue
                else:
                    result = False
                    break
        else:result=False

if result: print(2**int(n/2) % (10**9+7))
else:print(0)
### BUGGY CODE ###

import math
n=int(input())
nn=int(math.sqrt(n))
for i in range(1,n+1):
    min=int((nn+1)/3)
    min1=int((nn+1)/2)
    count=0
    for x in range(1,min+1):
        for y in range(x,min1+1):
            for z in range(y,nn+1):
                #print(x*x+y*y+z*z+x*y+y*z+z*x)
                if (x*x+y*y+z*z+x*y+y*z+z*x)==i:
                    if x==y and y==z and z==y:
                        count=count+1
                    elif x!=y and y!=z and z!=y:
                        count=count+6
                    else:
                        count=count+3
    print(count)


### FIXED CODE ###

import math
n=int(input())
for i in range(1,n+1):
    nn=int(math.sqrt(i))
    min=int((nn+1)/math.sqrt(3))
    min1=int((nn+1)/math.sqrt(2))
    count=0
    for x in range(1,min+1):
        for y in range(x,min1+1):
            for z in range(y,nn+1):
                #print(x*x+y*y+z*z+x*y+y*z+z*x)
                if (x*x+y*y+z*z+x*y+y*z+z*x)==i:
                    if x==y and y==z and z==x:
                        count=count+1
                    elif x!=y and y!=z and z!=x:
                        count=count+6
                    else:
                        count=count+3
    print(count)
### BUGGY CODE ###

import re

N, Q = map(int, input().split())
S = input()
P = []
for _ in range(Q):
	l, r = map(int, input().split())
	P.append((l, r))
for p in P:
	#print(p)
	s = S[p[0] - 1:p[1]]
	ac = re.findall("AC", s)
	print(len(ac))
	#print(s)
	#print(ac)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()

# S         * A C * A C C
# sumlist   0 0 1 1 1 2 2
sumlist = [0]
for i in range(1, len(S)):
	sumlist.append(sumlist[-1])
	if S[i - 1] == "A" and S[i] == "C":
		sumlist[-1] += 1

query = []
for i in range(Q):
	l, r = map(int, input().split())
	query.append(dict(l=l-1, r=r-1))

for q in query:
	print(sumlist[q["r"]] - sumlist[q["l"]])
### BUGGY CODE ###

# -*- coding: utf-8 -*-


class Node():
    def __init__(self, loc=None, left=None, right=None):
        self.loc = loc
        self.l = left
        self.r = right

    def __repr__(self):
        return "{}".format(self.loc)


class Point():
    def __init__(self, id, xy):
        self.id = int(id)
        self.x = int(xy[0])
        self.y = int(xy[1])

    def __repr__(self):
        return "{}".format(self.id)


if __name__ == '__main__':

    n = int(input())
    P = [Point(i, input().split(" ")) for i in range(n)]
    q = int(input())
    Q = [list(map(int, input().split(" "))) for _ in range(q)]
    T = [None] * n

    np = 0

    def make2DTree(l, r, depth):
        global np
        if l >= r:
            return None

        mid = (l + r) // 2
        t = np
        np += 1
        if depth % 2 == 0:
            P[l:r] = sorted(P[l:r], key=lambda p: p.x)
        else:
            P[l:r] = sorted(P[l:r], key=lambda p: p.y)

        T[t] = Node(loc=mid)
        T[t].l = make2DTree(l, mid, depth + 1)
        T[t].r = make2DTree(mid + 1, r, depth + 1)

        return t

    def find(v, sx, tx, sy, ty, depth, ans):
        x = P[T[v].loc].x
        y = P[T[v].loc].y

        if (sx <= x <= tx) and (sy <= y <= ty):
            ans.append(P[T[v].loc].id)

        if depth % 2 == 0:
            if T[v].l is not None and sx <= x:
                find(T[v].l, sx, tx, sy, ty, depth + 1, ans)
            if T[v].r is not None and x <= tx:
                find(T[v].r, sx, tx, sy, ty, depth + 1, ans)

        else:
            if T[v].l is not None and sy <= y:
                find(T[v].l, sx, tx, sy, ty, depth + 1, ans)
            if T[v].r is not None and y <= ty:
                find(T[v].r, sx, tx, sy, ty, depth + 1, ans)

    root = make2DTree(0, n, 0)

    for sx, tx, sy, ty in Q:
        ans = []
        find(root, sx, tx, sy, ty, 0, ans)
        ans.sort()
        if ans:
            print("\n".join(map(str, ans)))
        print("")



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right

if __name__ == '__main__':

    P = [tuple(map(int, input().split())) + (i,)
         for i in range(int(input()))]  # (x,y,i)
    P.sort()
    root = int(math.sqrt(len(P)))
    low = [x for x, y, i in P[::root]]
    high = [x for x, y, i in P[root - 1::root]] + [float('inf')]

    # disjoint subsets (ordered by y) of P
    P = [sorted(P[i:i + root], key=itemgetter(1))
         for i in range(0, len(P), root)]
    P = [([y for x, y, i in Pi], Pi)
         for Pi in P]  # ([y in subsets], [subsets])
    q = int(input())
    Q = [list(map(int, input().split(" "))) for _ in range(q)]

    for sx, tx, sy, ty in Q:
        ret = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            k, v = P[i]
            for i in range(bisect_left(k, sy), bisect_right(k, ty)):
                if sx <= v[i][0] <= tx:
                    ret.append(v[i][2])
        if ret:
            ret.sort()
            print('\n'.join(map(str, ret)))
        print()
### BUGGY CODE ###

n,k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')]*n
dp[0] = 0
if n == 2:
    print(h[1]-h[0])
else:
    for i in range(1,n):
        for j in range(1,k+1):
            if i >= j:
                dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
    print(dp[n-1])

                

### FIXED CODE ###

n,k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
inf = 10**10
dp = [inf]*n
dp[0] = 0
 
for i in range(1,n):
    dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]) for j in range(min(i,k)+1))
 
print(dp[n-1])
### BUGGY CODE ###

import numpy as np
import sys
lines = sys.stdin.read().splitlines()
# n, m, q = [int(item) for item in input().split(" ")]
n, m, q = [int(item) for item in lines[0].split(" ")]

end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
#     end[i] = [int(item) for item in input().split(" ")]
    end[i] = [int(item) for item in lines[1+i].split(" ")]

for i in range(q):
#     query[i] = [int(item) for item in input().split(" ")]
    query[i] = [int(item) for item in lines[1+m+i].split(" ")]

a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
for item in query:
    print(np.sum(a[(item[0]-1):, :item[1]]))

### FIXED CODE ###

import numpy as np
n, m, q = [int(item) for item in input().split(" ")]
# n, m, q = [int(item) for item in lines[0].split(" ")]

end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
    end[i] = [int(item) for item in input().split(" ")]
#     end[i] = [int(item) for item in lines[1+i].split(" ")]

for i in range(q):
    query[i] = [int(item) for item in input().split(" ")]
#     query[i] = [int(item) for item in lines[1+m+i].split(" ")]

a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
b = np.cumsum(a[::-1,:], axis=0)[::-1,:]
c = np.cumsum(b, axis=1)
for item in query:
    print(c[item[0]-1, item[1]-1])
    # print(np.sum(a[(item[0]-1):, :item[1]]))
### BUGGY CODE ###

import numpy as np
N = input()
N = int(N)
S = {}
n_anagram = 0
D = {"a":2, "b":3, "c":5, "d":7, "e":11, "f":13,"g":17, "h":19, "i":23, "j":29, "k":31, "l":37, "m":41, "n":43,
"o":47, "p":53, "q":57, "r":59, "s":61, "t":67, "u":71, "v":73, "w":79, "x":83, "y":87, "z":1}

for i in range(N):
    s = input()
    s1 = [D[x] for x in s]
    s2 = np.prod(s1)
    if s2 in S:
        n_anagram= n_anagram + S[s2]
        S[s2] += 1
    else:
        S[s2] = 1
    
print(n_anagram)

### FIXED CODE ###

import numpy as np
N = input()
N = int(N)
Sdict = {}
n_anagram = 0
D = {"a":2, "b":3, "c":5, "d":7, "e":11, "f":13,"g":17, "h":19, "i":23, "j":29, "k":31, "l":37, "m":41, "n":43,
"o":47, "p":53, "q":59, "r":61, "s":67, "t":71, "u":73, "v":79, "w":83, "x":89, "y":97, "z":1}

S = [input() for _ in range(N)]

for s in S:
    s1 = [D[x] for x in s]
    s2 = np.prod(s1)

    if s2 in Sdict:
        n_anagram = n_anagram + Sdict[s2]
        Sdict[s2] += 1
    else:
        Sdict[s2] = 1
   
print(n_anagram)
### BUGGY CODE ###

l,r=map(int,input().split())
if l-r>2019:
    print(0)
else:
    s=2019
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            s=min(s,i*j%2019)
    print(s)


### FIXED CODE ###

l,r=map(int,input().split())
x=l//2019
y=r//2019
if y-x>=1:
    print(0)
else:
    s=2019
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            s=min(s,i*j%2019)
    print(s)
### BUGGY CODE ###

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

ans = 0
dp = [0] * N
for i in range(N - 1):
    dp2 = dp[:]
    for j in range(i + 1, N):
        if S[i] == S[j] and j - i > dp2[j-1]:
            dp[j] = dp2[j-1] + 1
            ans = max(ans, dp[j])
        else:
            dp[j] = 0

print(ans)

### FIXED CODE ###

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

dp = [[0 for _ in range(N)] for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            tmp = 1
            if i > 0:
                tmp += dp[i - 1][j - 1]
            if j - i < tmp:
                continue
            dp[i][j] = tmp
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

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

res = 0

for i in range(N-2):
    L1 = L[i+1:]
    a = L[i]
    for j in range(len(L1)-1):
        L2 = L1[j+1:]
        b = L1[j]
        sup = a + b
        inf = max(a-b,b-a)
        SL2 = set(L2)
        test = {x for x in range(inf+1,sup)}
        Scan = SL2 & test
        if len(Scan) == 0:
            break

        LScan = list(Scan)
        M = len(LScan)
        for c in LScan:
            res += L2.count(c)

print(res)


### FIXED CODE ###

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

v = L[:]
v.sort()

res = 0

import bisect

for i in range(N-2):
    a = v[i]
    for j in range(i+1,N-1):
        b = v[j]
        sup = a + b
        #inf = max(a-b,b-a)
        iterS = bisect.bisect_left(v,sup)
        #iterI = bisect.bisect_left(v,inf+1)
        #print(a,b,sup,inf,iterS,iterI)
        res += iterS - (j+1)

print(res)
### BUGGY CODE ###

M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [-1]*(k+1)
for i in range(k, 0, -1):
    tmp = ((k // i) ** n) % M
    tmp -= sum(nums[(2*i)::i])
    nums[i] = tmp
print(sum((i)*nums[i]%M for i in range(len(nums)))%M)

### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = pow(k // i, n, M)
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    
# print(sum((i)*nums[i]%M for i in range(len(nums)))%M)
print((np.arange(k+1) * nums).sum()%M)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
max_len = len(format(max(a), "b"))
a = [format(a[i], "b") for i in range(n)]
b = [0 for _ in range(max_len)]

for i in range(n):
    for j in range(1, 1+len(a[i])):
        if int(a[i][-j]):
            b[j-1] += 1

result = 0
for i in range(max_len):
    r = b[i]*(n-b[i])%mod
    r = (r*2**i) %mod
    result += r
print(result%mod) 

### FIXED CODE ###

import numpy as np
mod = 10**9+7
n = int(input())
a = np.fromstring(input(), dtype = np.int64, sep = ' ')

result = 0
for i in range(60):
    count_one = int((a&1).sum())
    result += count_one*(n-count_one)*(2**i)
    a >>= 1
print(result%mod)
### BUGGY CODE ###

S = input()
N = len(S)
S = list(S)
S.reverse()

dp = [[0]*13 for _ in range(N + 1)]
dp[0][0] = 1
mod = 10**9+7
pow10 = 1
for i in range(1, N + 1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j + k*pow10) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j+int(S[i-1])*pow10) % 13] = dp[i-1][j]
    pow10 *= 10
    for j in range(13):
        dp[i][j] %= mod

print(dp[N][5])


### FIXED CODE ###

S = input()
N = len(S)
S = list(S)
S.reverse()

dp = [[0]*13 for _ in range(N + 1)]
dp[0][0] = 1
mod = 10**9+7
pow10 = 1
for i in range(1, N + 1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j + k*pow10) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j+int(S[i-1])*pow10) % 13] = dp[i-1][j]
    pow10 = (pow10 * 10) % 13
    for j in range(13):
        dp[i][j] %= mod

print(dp[N][5])
### BUGGY CODE ###

def main():
    S = input()

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for s in reversed(S):
        nextdp = [0] * 13
        if s == '?':
            for i in range(10):
                for j in range(13):
                    nextdp[(i * digit + j) % 13] += dp[j]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(i * digit + j) % 13] %= mod
        else:
            k = int(s)
            for j in range(13):
                nextdp[(k * digit + j) % 13] += dp[j]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(k * digit + j) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()

### FIXED CODE ###

def main():
    S = list(input())

    dp = [0] * 13
    dp[0] = 1
    mod = 10**9 + 7
    digit = 1
    for i in range(len(S)-1,-1,-1):
        nextdp = [0] * 13
        if S[i] == '?':
            for j in range(10):
                for k in range(13):
                    nextdp[(j * digit + k) % 13] += dp[k]
                    # あらかじめ10*9 + 7で割って余りを出しておく
                    nextdp[(j * digit + k) % 13] %= mod
        else:
            j = int(S[i])
            for k in range(13):
                nextdp[(j * digit + k) % 13] += dp[k]
                # あらかじめ10*9 + 7で割って余りを出しておく
                nextdp[(j * digit + k) % 13] %= mod
        
        digit *= 10
        # A * 桁数の13で割ったあまりは (A % 13) * (桁数 % 13)のため、桁数を13で割っておく
        digit %= 13
        dp = nextdp
    
    print(dp[5])

main()
### BUGGY CODE ###

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
ans=0
for i in range(N):
    a=A[i]
    D=make_divisors(a)
    #print(D)
    L=A[:i]+A[i+1:]
    for d in D:
        if d in L:
            ans+=1
            break
print(N-ans)


### FIXED CODE ###

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




MAX=max(A)
nums=[0]*(MAX)

ans=0

for i in range(N):
    a=A[i]
    kousin=True
    if i!=0:
        if A[i-1]==a:
            kousin=False
    if i!=N-1:
        if a==A[i+1]:
            kousin=False

    if nums[a-1]==0 and kousin:
        ans+=1
        
                
        if a>MAX//2:
            continue
            

    count=1
    num=a
    while num<=MAX:
        nums[num-1]+=1
        count+=1
        num=a*count
    
#print(nums)
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

for i in range(N):
  for j in range(int(input())):
  	x, y = map(int,input().split())
  	A[i][y][x-1] = True

upper = 0

for i in range(2**N):
  mask = (1 & i >> np.arange(N)).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  m2 = np.repeat([mask], s, axis=0).reshape(-1)
  aa = A[mask]
  a0 = aa[:,0].reshape(-1)
  if np.any(m2[a0]!=0): continue
  a1 = aa[:,1].reshape(-1)
  if np.any(m2[a1]!=1): continue
  upper = s

print(upper)

### FIXED CODE ###

import numpy as np

N = int(input())
A = np.zeros((N,2,N), dtype=bool) # A = {([false],[true]),,}

for i in range(N):
  for j in range(int(input())):
  	x, y = map(int,input().split())
  	A[i][y][x-1] = True

upper = 0

def hantei(mask):
  for a in A[mask]:
    if np.any(mask[a[0]]): return False
    if not(np.all(mask[a[1]])): return False
  return True

seed = 1 << np.arange(N)

for i in range(2**N):
  mask = (seed & i).astype(bool)
  s = np.sum(mask)
  if s <= upper: continue
  if hantei(mask): upper = s

print(upper)
### BUGGY CODE ###

#頂点を見た時に，枝分かれの本数に応じてansを更新

import math
import sys
input = sys.stdin.readline

mod=10**9+7

def permu(a,b):
    c=1
    for i in range(b):
        c*=(a-i)
    return c

N,K=map(int,input().split())
adj=[[] for _ in range(N)]
dep=[0]*N

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

#各深さにノードが何個あるか
q=[]
q.append([0,-1,0])#node,parent,depth
dep[0]+=1

ans=1
while q!=[]:
    v,p,d=q.pop()
    K2=max(K-2,K-d-1)
    l=len(adj[v])
    P=permu(K2,max(l-d,l-1))
    ans*=P
    ans%=mod
    for i in range(l):
        next_v=adj[v][i]
        if next_v!=p:
            q.append([next_v,v,d+1])
            dep[d+1]+=1

print((ans*K)%mod)

### FIXED CODE ###

#頂点を見た時に，枝分かれの本数に応じてansを更新
#permutationのリストを先に作っておく

import sys
input = sys.stdin.readline

mod=10**9+7


N,K=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(N - 1)]
adj=[[] for _ in range(N)]

for a,b in ab:
    adj[a-1].append(b-1)
    adj[b-1].append(a-1)
    
    
#順列(K-2)Piを先に
P=[1]
for i in range(N):
    P.append((P[-1]*(K-2-i))%mod)
    

q=[(0,-1,0)]#node,parent,depth

ans=1
while q!=[]:
    v,p,d=q.pop()
    #深さ0or1で塗ることができる色数は異なる
    l=len(adj[v])
    if d==0:
        ans*=(K-1)
    ans*=(P[l-1])
    ans%=mod
    for i in range(l):
        next_v=adj[v][i]
        #葉は追加しない
        if next_v!=p and len(adj[next_v])!=1:
            q.append((next_v,v,d+1))
if N==1:
    ans=1
print((ans*K)%mod)
### BUGGY CODE ###

import bisect as bis
Q = int(input())
minval = 0
argminval = -(10**9)
L, R = [-(10**9)], [10**9]
lenL, lenR = 0, 0

def listupdate(items, new):
    ind = bis.bisect_left(items, new)
    ret = items[:ind]+[new]+items[ind:]
    return ret

for _ in range(Q):
    qi = list(map(int, input().split()))
    if qi[0] == 1:
        ai, bi = qi[1], qi[2]
        LC, RC = L[-1], R[0]
        if lenL == lenR:
            if ai < RC:
                L = listupdate(L, ai)
            else:
                L = listupdate(L, RC)
                R = listupdate(R[1:], ai)
            lenL += 1
            argminval = L[-1]
            minval += abs(argminval - ai) + bi
        else:
            if ai < LC:
                L = listupdate(L[:-1], ai)
                R = listupdate(R, LC)
            else:
                R = listupdate(R, ai)
            lenR += 1
            minval += abs(argminval - ai) + bi
            argminval = L[-1]
    else:
        print("{} {}".format(argminval, minval))

### FIXED CODE ###

import heapq as hq
Q = int(input())
minval = 0
argminval = -(10**9)
#aを大きい方と小さい方に分けて最小ヒープで管理(Lは最大が欲しいので-1掛けておく)
L, R = [10**9], [10**9]
lenL, lenR = 0, 0

for _ in range(Q):
    qi = list(map(int, input().split()))
    if qi[0] == 1:
        ai, bi = qi[1], qi[2]
        LC, RC = -1*L[0], R[0] #左右それぞれで中央に一番近いもの
        if lenL == lenR:
            if ai < RC:
                #Lにaiを追加
                hq.heappush(L, -1*ai)
            else:
                #RCをLに移動, Rにaiを追加
                hq.heappop(R)
                hq.heappush(L, -1*RC)
                hq.heappush(R, ai)
            lenL += 1
            #新しいargminで最小値更新
            argminval = -1*L[0]
            minval += abs(argminval - ai) + bi
        else:
            if ai < LC:
                #LCをRに移動, Lにaiを追加
                hq.heappop(L)
                hq.heappush(L, -1*ai)
                hq.heappush(R, LC)
            else:
                #Rにaiを追加
                hq.heappush(R, ai)
            lenR += 1
            #古いargminで最小値更新
            minval += abs(argminval - ai) + bi
            argminval = -1*L[0]
    else:
        print("{} {}".format(argminval, minval))