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

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    for j in range(N):
        if S[j] == S[-1]:
            dp[N-1][j] = 1

    for i in range(N-2,-1,-1):
        for j in range(N-2,-1,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1

    res = 0
    for i in range(N):
        for j in range(i+1,N):
            l = dp[i][j]
            if j >= i+l:
                res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools


def solve(N: int, S: str):
    dp = [[0 for _ in range(N)] for _ in range(N)]

    for i in range(N):
        if S[i] == S[-1]:
            dp[i][N-1] = 1

    res = 0
    for i in range(N-2,-1,-1):
        for j in range(N-2,i,-1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                l = dp[i][j]
                if j >= i+l:
                    res = max(res,l)

    print(res)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

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


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

w = [0 for i in range(N+1)]
v = [0 for i in range(N+1)]

for i in range(N):
    w[i+1],v[i+1] = map(int, input().split())

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #品物0個のときはもちろん価値は0
    if i == 0:
        return 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    if W2 < w[i]:
        return nap(i-1,W2)
    #品物１つで制約OK→品物一つの価値がnapの価値        
    if i == 1:
        return v[i]

    return max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
            
print(nap(N,W))


### FIXED CODE ###


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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
Wmin = min(w)

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))
### BUGGY CODE ###

def heapify(values):
  n = len(values)
  for i in range(1,n):
    upheap(values,i)
    print(' '.join(map(str, values)))

def upheap(values, i):
  while parent(i) >= 0:
    if values[i] > values[parent(i)]:
      values[i], values[parent(i)] = values[parent(i)], values[i]
      i = parent(i)
    else:
      break

def pop(values):
  ret = values[0]
  values[0], values[len(values)-1] = values[len(values)-1], values[0]
  del values[len(values)-1]
  downheap(values)
  return ret

def push(values, x):
  values.append(x)
  upheap(values, len(values)-1)

def downheap(values):
  i = 0
  while left(i) < len(values) or right(i) < len(values):
    l = left(i)
    r = right(i)
    if l >= len(values):
      m = r
    elif r >= len(values):
      m = l
    else:
      m = r
      if values[l] > values[r]:
        m = l
    if values[i] < values[m]:
      values[m], values[i] = values[i], values[m]
    else:
      break
    i = m

def parent(i):
  i = i+1
  return i//2-1

def left(i):
  i = i+1
  return i*2-1

def right(i):
  i = i+1
  return i*2

values = []
while True:
  line = input()
  if line.startswith('end'):
    break
  elif line.startswith('extract'):
    print(pop(values))
  elif line.startswith('insert'):
    num = int(line.split(' ')[1])
    push(values, num)

### FIXED CODE ###

from sys import stdin

def max_heapify(A, i):
    l = i*2
    r = i*2+1
    largest = i
    if l <= A[0] and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= A[0] and A[largest] < A[r]:
        largest = r

    if largest != i:
        A[largest],A[i] = A[i],A[largest]
        max_heapify(A,largest)

heap = [0]*2000000
for c in stdin:
    if c[0] == 'i':
        heap[0] += 1
        heap[heap[0]] = int(c[7:])
        i = heap[0]
        p = i/2
        while p > 0 and heap[p] < heap[i]:
            heap[p],heap[i] = heap[i],heap[p]
            i = p
            p = i/2
    elif c[1] == 'x':
        print heap[1]
        heap[1] = heap[heap[0]]
        heap[0] -= 1
        max_heapify(heap,1)
    else:
        break
### BUGGY CODE ###

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

dp = [0]*(N+1)
for i in range(1,N+1):
    for j in range(3):
        if i-A[j] >= 0:
            dp[i] = max(dp[i],dp[i-1]+1,dp[i-A[j]]+B[j])
        else:
            dp[i] = max(dp[i],dp[i-1]+1)

M = dp[N]            
dp = [0]*(M+1)

for i in range(1,M+1):
    for j in range(3):
        if i-B[j] >= 0:
            dp[i] = max(dp[i],dp[i-1]+1,dp[i-B[j]]+A[j])
        else:
            dp[i] = max(dp[i],dp[i-1]+1)
    
print(dp[M])

### FIXED CODE ###

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

dp = [0]*(N+1)
for j in range(3):
    for i in range(1,N+1):
        if i-A[j] >= 0:
            dp[i] = max(dp[i],dp[i-1]+1,dp[i-A[j]]+B[j])
        else:
            dp[i] = max(dp[i],dp[i-1]+1)

M = dp[N]            
dp = [0]*(M+1)

for j in range(3):
    for i in range(1,M+1):
        if i-B[j] >= 0:
            dp[i] = max(dp[i],dp[i-1]+1,dp[i-B[j]]+A[j])
        else:
            dp[i] = max(dp[i],dp[i-1]+1)
    
print(dp[M])
### BUGGY CODE ###

import numpy as np
N,K = map( int, input().split() )
h_list = list ( map( int, input().split() ) )
for i in range(150):
    h_list.append(0)
h_list = np.array(h_list)
result_list = np.array([10**10]*(N+150))
result_list[0] = 0
for i in range(N):
    for j in range(1,K+1):
        result_list[i+j] = min(result_list[i+j], result_list[i] + abs( ( h_list[i+j] - h_list[i]) ) )
print(result_list[N-1])

### FIXED CODE ###

N,K = map( int, input().split() )
H = list( map( int, input().split() ) )
dp = [0]*N
for i,Hi in enumerate(H[1:],1):
    s = max(0,i-K)
    dp[i] = min( [ t + abs( Hi - hl ) for hl,t in zip(H[s:i], dp[s:i]) ] )
print(dp[N-1])
### BUGGY CODE ###

n, m = map(int, input().split())
peaks = [0] + list(map(int, input().split())) # '0'が余計

ans =[_ for _ in range(n+1)] # '0'が余計

for i in range(m):
    x,y = map(int, input().split())
    if peaks[x] > peaks[y]:
        if y in ans:
            ans.remove(y)
    elif peaks[x] < peaks[y]:
        if x in ans:
            ans.remove(x)
    else:
        if x in ans:
            ans.remove(x)
        if y in ans:
            ans.remove(y)

print(len(ans) -1)


### FIXED CODE ###

n, m = map(int,input().split())
h = list(map(int,input().split()))
l = [list(map(int, input().split())) for _ in range(m)]

x = [[] for _ in range(n)]

for i in range(m):
    if l[i][1] not in x[l[i][0]-1]:
        x[l[i][0]-1].append(l[i][1])

for j in range(m):
    if l[j][0] not in x[l[j][1]-1]:
        x[l[j][1]-1].append(l[j][0])

y = 0
for a in range(n):
    for c in range(len(x[a])):
        if h[a] <= h[x[a][c]-1]:
            break
    else:
        y += 1

print(y)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left
from collections import defaultdict

def main():
    N = int(input())
    A = [int(i) for i in input().split()]

    # IDX[n]: nのindex
    IDX = defaultdict(int)
    for idx,a in enumerate(A):
        IDX[a] = idx

    ans = 0
    T = [-1, N]
    for n in range(1, N + 1):
        idx = bisect_left(T, IDX[n])
        T = T[:idx] + [IDX[n]] + T[idx:]
        ans += (T[idx] - T[idx-1]) * (T[idx+1] - T[idx]) * n

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
from collections import defaultdict
class SqrtSet:
    def __init__(self, block_limit=201):
        self.key = []
        self.child = [[]]
        self.block_limit = block_limit
 
    def search_lower(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_left(self.key, key)
        if i != 0:
            ret = self.key[i - 1]
        block = self.child[i]
        i = bisect.bisect_left(block, key)
        if i != 0:
            ret = block[i - 1]
        return ret
        
    def search_higher(self, key):
        if key is None:
            return None
        ret = None
        i = bisect.bisect_right(self.key, key)
        if i != len(self.key):
            ret = self.key[i]
        block = self.child[i]
        i = bisect.bisect_right(block, key)
        if i != len(block):
            ret = block[i]
        return ret
 
    def insert(self, key):
        i = bisect.bisect(self.key, key)
        block = self.child[i]
        bisect.insort(block, key)
        if len(block) == self.block_limit:
            sep = self.block_limit // 2
            self.key.insert(i, block[sep])
            self.child.insert(i + 1, block[sep + 1:])
            self.child[i] = block[:sep]

def main():
    N = int(input())
    A = [int(i) for i in input().split()]

    # IDX[n] <-> A.index(n)
    IDX = defaultdict(int)
    for idx,a in enumerate(A):
        IDX[a] = idx

    SS = SqrtSet()
    SS.insert(-1)
    SS.insert(N)

    ans = 0
    for n in range(1, N + 1):
        H = SS.search_higher(IDX[n])
        L = SS.search_lower(IDX[n])
        ans += (IDX[n] - L) * (H - IDX[n]) *  n
        SS.insert(IDX[n])

    print(ans)

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

N, M = map(int, input().split())
S = input()
if N <= M:
  print(N)
  exit()
if '1'*M in S:
  print(-1)
  exit()
count = [0 for _ in range(N+1)]
for k in range(M+1):
  if S[k] == '1':
    count[k] = -1
  else:
    count[k] = k
from collections import deque
now = M
while now < N:
  now += 1
  cnt = 0 
  before = deque(count[now-M:now])
  a = before.popleft()
  if S[now] == '1':
    count[now] = -1
    continue
  else:
    if a > 0:
      count[now] = M
    else:
      while a  < 0:
        cnt += 1
        a = before.popleft()
      count[now] = M - cnt

c = 0
ans = ''
while c < N:
  ans = str(count[-1-c]) + ' ' + ans
  c += count[-1-c]

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = input()
if N <= M:
  print(N)
  exit()
if '1'*M in S:
  print(-1)
  exit()

from collections import deque
count = deque([])
for k in range(M+1):
  if S[k] == '1':
    count.append(-1)
  else:
    count.append(k)
sgn = deque([])
k = 0
while k < N:
  k += 1
  if S[k] == '0':
    sgn.append(M)
  else:
    d = 0
    while k < N:
      if S[k] == '1':
        k += 1
        d += 1
        continue
      else:
        break
    while d > 0:
      sgn.append(M-d)
      d -= 1
    sgn.append(M)
now = M
while now < N:
  now += 1
  a = sgn.popleft()
  if S[now] == '1':
    count.append(-1)
  else:
    count.append(a)
count = list(count)  
c = 0
ans = ''
while c < N:
  ans = str(count[-1-c]) + ' ' + ans
  c += count[-1-c]

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

A, B,C,D=map(int,input().split())

while(True):
    C=C-B
    if(C==0):
        print("Yes")
        break
    A=A-D
    if(A==0):
        print("No")
        break


### FIXED CODE ###

a,b,c,d = (int(x) for x in input().split())
 
while(True):
    c-=b
    if(c <= 0):
        print("Yes")
        break
    a-=d
    if(a <= 0):
        print("No")
        break
### BUGGY CODE ###

n = int(input())
s = input()

password = []
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            p = s[i] + s[j] + s[k]
            if not p in password:
                password.append(p)
print(len(password))

### FIXED CODE ###

n = int(input())
s = input()

cnt = 0
for i in range(10):
    s_ = s
    if str(0) in s_:
        s_ = s_[s_.index(str(0))+1:]
        if str(0) in s_:
            s_ = s_[s_.index(str(0))+1:]
            if str(i) in s_:
                cnt += 1

for i in range(10,100):
    s_ = s
    if str(0) in s_:
        s_ = s_[s_.index(str(0))+1:]
        if str(i)[0] in s_:
            s_ = s_[s_.index(str(i)[0])+1:]
            if str(i)[1] in s_:
                cnt += 1

for i in range(100,1000):
    s_ = s
    if str(i)[0] in s_:
        s_ = s_[s_.index(str(i)[0])+1:]
        if str(i)[1] in s_:
            s_ = s_[s_.index(str(i)[1])+1:]
            if str(i)[2] in s_:
                cnt += 1  

print(cnt)
### BUGGY CODE ###

s = input()
n = len(s)
dp = [0]

for i, c in enumerate(s):
    new = [0] * (i + 2)
    for j in range(i % 2, i + 1, 2):
        new[j + 1] = dp[j] - int(c == 'p')
        if j:
            new[j - 1] = dp[j] + int(c == 'g')
    dp = new

print(max(dp))


### FIXED CODE ###

s = input()
print(len(s) // 2 - s.count('p'))
### BUGGY CODE ###

from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(int)
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   dic[Fraction(A,B)]+=1
ans=1
for k in dic:
 if -1/k in dic:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
  ans%=mod
  dic[k]=0
  dic[-1/k]=0
 else:
  ans*=pow(2,dic[k],mod)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = [0]
visited = [False for i in range(n)]
while len(s) > 0:
    x = s.pop(0)
    visited[x] = True
    sp[x] += px[x]
    for xc in d[x]:
        if not visited[xc]:
            s.append(xc)
            sp[xc] += sp[x]
for i in range(n):
    print(sp[i])


### FIXED CODE ###

from collections import deque
n, q = map(int,input().split())
d = [[] for i in range(n)]
for i in range(n-1):
    ai, bi = map(int,input().split())
    d[ai-1].append(bi-1)
    d[bi-1].append(ai-1)
#point
px = [0 for i in range(n)]
for i in range(q):
    pi,xi = map(int,input().split())
    px[pi-1] += xi
sp = [0 for i in range(n)]
s = deque()
s.append(0)
visited = [False for i in range(n)]
while len(s) > 0:
    x = s.popleft()
    visited[x] = True
    sp[x] += px[x]
    for xc in d[x]:
        if not visited[xc]:
            s.append(xc)
            sp[xc] += sp[x]
for i in range(n):
    print(sp[i])
### BUGGY CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
hor = [[0] * w for _ in range(h)]
ver = [[0] * w for _ in range(h)]

for i in range(h):
    now = 0
    for j in range(w):
        if s[i][j] == '#':
            now = 0
        else:
            now += 1
            hor[i][j] = now

for j in range(w):
    now = 0
    for i in range(h):
        if s[i][j] == '#':
            now = 0
        else:
            now += 1
            ver[i][j] = now

for i in range(h-1, -1, -1):
    now = 0
    for j in range(w-1, -1, -1):
        if s[i][j] == '#':
            now = 0
        else:
            now = max(now, hor[i][j])
            hor[i][j] = now

for j in range(w-1, -1, -1):
    now = 0
    for i in range(h-1, -1, -1):
        if s[i][j] == '#':
            now = 0
        else:
            now = max(now, ver[i][j])
            ver[i][j] = now

res = 0
for i in range(h):
    for j in range(w):
        res = max(hor[i][j] + ver[i][j] - 1, res)
print(res)


### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
hor = [[0] * w for _ in range(h)]
ver = [[0] * w for _ in range(h)]

for i in range(h):
    now = 0
    for j in range(w):
        if s[i][j] == '#':
            now = 0
        else:
            now += 1
            hor[i][j] = now

for j in range(w):
    now = 0
    for i in range(h):
        if s[i][j] == '#':
            now = 0
        else:
            now += 1
            ver[i][j] = now

for i in range(h-1, -1, -1):
    now = 0
    for j in range(w-1, -1, -1):
        if s[i][j] == '#':
            now = 0
        else:
            now = max(now, hor[i][j])
            hor[i][j] = now

for j in range(w-1, -1, -1):
    now = 0
    for i in range(h-1, -1, -1):
        if s[i][j] == '#':
            now = 0
        else:
            now = max(now, ver[i][j])
            ver[i][j] = now

res = 0
for i in range(h):
    for j in range(w):
        res = max(hor[i][j] + ver[i][j] - 1, res)
print(res)
### BUGGY CODE ###

N, K = (int(x) for x in input().split())
if N%K == 0:
  N = 0
else:
  while N >= abs(N-K):
    N = abs(N-K)
print(N)

### FIXED CODE ###

N, K = (int(x) for x in input().split())
a = N%K
if a >= K-a:
  print(K-a)
else:
  print(a)
### BUGGY CODE ###

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

babies = [(a, i) for i, a in enumerate(a)]
babies.sort(reverse=True)

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
ans = 0
for l in range(n):
  for r in range(n):
    if l+r == n:
      ans = max(ans, dp[l][r])
      break
    activeness, ind = babies[l+r]
    dp[l+1][r] = max(dp[l+1][r], dp[l][r] + activeness * abs(ind - l))
    dp[l][r+1] = max(dp[l][r+1], dp[l][r] + activeness * abs(ind - (n - 1 - r)))
print(ans)


### FIXED CODE ###

n = int(input())
a = map(int, input().split())
babies = [(a, i) for i, a in enumerate(a)]
babies.sort(reverse=True)

dp = [[0]*(n+1) for i in range(n+1)]

ans = 0

for l in range(n):
  for r in range(n):
    if l+r == n:
      ans = max(ans, dp[l][r])
      break
    activeness, ind = babies[l+r]
    dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(ind - l) * activeness)
    dp[l][r+1] = max(dp[l][r+1], dp[l][r] + abs(ind - (n-1-r)) * activeness)
print(ans)
### BUGGY CODE ###

n = int(input())
ac = 0
for a in range(1,n):
    be = n // a
    for b in range(1,be+1):
        c = n - a * b
        if c > 0:
            ac += 1
print(ac)

### FIXED CODE ###

n = int(input())
ac = 0
for a in range(1,n):
    be = (n-1) // a
    ac += be
print(ac)
### BUGGY CODE ###

s = input()
tn = len(s)
n = len(s)


while True:
    t = 0
    i = 0
    while i < n - 1:
        if s[i] != s[i+1]:
            s = s[:i] + s[i+2:]
            if t == 0:
                t = 1
            n = len(s)
        else: i += 1
    if t == 0: break

print(tn - n)

### FIXED CODE ###

s = input()
one = 0
zero = 0
for i in s:
    if i == "0": zero += 1
    else: one += 1
print(len(s) - abs(one - zero))
### BUGGY CODE ###

##!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


def main():
    pass


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

a, b = map(int, input().split())
c = 1
for i in range(a, b+1):
    c *= i
if c>0:
    print("Positive")
elif c<0:
    print("Negative")
else:
    print("Zero")

### FIXED CODE ###

a, b = map(int, input().split())
if a>0 and b>0:
    print("Positive")
elif a==0 or b==0:
    print("Zero")
elif (a>0 and b<0) or (a<0 and b>0):
    print("Zero")
elif ((a+b)+1)%2==0:
    print("Positive")
else:
    print("Negative")
### BUGGY CODE ###

def permutation_modp(n,k):
    ans=1
    for i in range(k):
        ans*=(n-i)
    return ans%1000000007
num_vertax,num_coler=map(int,input().split())
ver_array=[0 for i in range(num_vertax)]
for i in range(num_vertax-1):
    a,b=map(int,input().split())
    ver_array[a-1]+=1
    ver_array[b-1]+=1
ans=num_coler
top=1
for ver in ver_array:
    ans=(ans%1000000007)*permutation_modp(num_coler-2+top,ver+top-1)
    top=0
print(ans%1000000007)

### FIXED CODE ###

N,K=map(int,input().split())
mod=1000000007
path=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a=a-1
  b=b-1
  path[a].append(b)
  path[b].append(a)
#print(path)
  
abc=[False for i in range(N)] #0ならまだ塗ってない
 
abc[0]=True
cnt=0
ans=K%mod
nx=[]
for i in range(len(path[0])):
  child=path[0][i]
  if abc[child]:
    continue
  ans=ans*(K-1-cnt)
  ans=ans%mod
  cnt=cnt+1
  abc[child]=True
  nx.append(child)
while len(nx)>0:
  a=nx.pop()
  cnt=0
  for i in range(len(path[a])):
    child=path[a][i]
    if abc[child]:
      continue
    ans=ans*(K-2-cnt)
    ans=ans%mod
    cnt=cnt+1
    abc[child]=True
    nx.append(child)
      
print(ans%mod)
### BUGGY CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return (gcd(y, x % y))


ans = 0
k = int(input())

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)


### FIXED CODE ###

def gcd(x, y):
    if y == 0:
        return x
    else:
        return (gcd(y, x % y))


ans = 0
k = int(input())

for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)