Harryxun/stf_run huggingface dataset:
import math

def routing(s,g,route):
    ans=[]
    i=g
    while i!=-1:
        ans.append(i+1)
        i=route[i]
    return ans[::-1]

inf=100000
while True:
    n=input()
    if n==0:break
    L=[[inf]*n for i in range(n)]
    for i in range(n):
        L[i][i]=0
    B=[map(int,raw_input().split()) for i in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            ba,xa,ya=B[i]
            bb,xb,yb=B[j]
            ba,bb=ba-1,bb-1
            d=math.sqrt(pow(xa-xb,2)+pow(ya-yb,2))
            if d<=50:
                L[ba][bb]=L[bb][ba]=d

    m=input()
    for p in range(m):
        s,g=map(int,raw_input().split())
        s,g=s-1,g-1
        size=len(L)
        done=[s]
        dist=[inf]*size
        dist[s]=0
        route=[-1]*size
        i=s
        while len(done)<size:
            for j in range(size):
                if j in done:
                    continue
                if dist[j]>dist[i]+L[i][j]:
                    dist[j]=dist[i]+L[i][j]
                    route[j]=i
            min_node_size=inf
            for v,w in enumerate(dist):
                if v not in done and w<min_node_size:
                    min_node_size=w
                    min_node_num=v
            i=min_node_num
            done.append(min_node_num)
        if route[g]==-1:
            print 'NA'
        else:
            ans=routing(s,g,route)
            print " ".join(map(str,ans))

### FIXED CODE ###

import math

def dijkstra(s):
    d=[inf]*n
    pi=[inf]*n
    visited=[False]*n
    d[s]=0
    pi[s]=-1
    while True:
        mincost=inf
        for i in range(n):
            if not visited[i] and d[i]<mincost:
                mincost=d[i]
                u=i
        if mincost==inf:
            break
        visited[u]=True
        for v in range(n):
            if visited[v] or L[u][v]==inf:
                continue
            if d[u]+L[u][v]<d[v]:
                d[v]=d[u]+L[u][v]
                pi[v]=u
    return pi

def routing(pi,g):
    ans=[]
    i=g
    while i!=-1:
        ans.append(i+1)
        i=pi[i]
    return ans[::-1]

inf=100000
while True:
    n=input()
    if n==0:break
    L=[[inf]*n for i in range(n)]
    for i in range(n):
        L[i][i]=0
    B=[map(int,raw_input().split()) for i in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            ba,xa,ya=B[i]
            bb,xb,yb=B[j]
            ba,bb=ba-1,bb-1
            d=math.sqrt(pow(xa-xb,2)+pow(ya-yb,2))
            if d<=50:
                L[ba][bb]=L[bb][ba]=d
    m=input()
    for i in range(m):
        s,g=map(int,raw_input().split())
        s,g=s-1,g-1
        pi=dijkstra(s)
        if pi[g]==inf:
            print "NA"
        else:
            ans=routing(pi,g)
            print " ".join(map(str,ans))
import bisect
input = sys.stdin.readline


N = int(input())
A = list(map(int ,input().split()))
B = list(map(int ,input().split()))
C = list(map(int ,input().split()))
A.sort()
B.sort()
C.sort()
cnt = 0
for j in B:
    a_index = bisect.bisect_left(A, j)
    c_index = bisect.bisect_right(C, j)
    cnt += len(A[:a_index])*len(C[c_index:])
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int ,input().split()))
B = list(map(int ,input().split()))
C = list(map(int ,input().split()))
A.sort()
B.sort()
C.sort()
cnt = 0
for j in B:
    a_index = bisect.bisect_left(A, j)
    c_index = bisect.bisect_right(C, j)
    cnt += a_index*(N-c_index)
print(cnt)
import sys
i = int(input())
i = list(i)
for k in range(3):
  if i[k] == i[k+1]:
    print("Bad")
    sys.exit()
print("Good")

### FIXED CODE ###

import sys
i = input()
i = list(map(int,list(i)))
for k in range(3):
  if i[k] == i[k+1]:
    print("Bad")
    sys.exit()
print("Good")
n=input()
if n%2==0:
  print(n)
else:
  print(n*2)

### FIXED CODE ###

n=input()
if int(n)%2==0:
  print(n)
else:
  print(int(n)*2)
x = ""
for i in range(3):
    S = input()
    char_list = list(S)
    x = x + char_list[i]
print x

### FIXED CODE ###

x = ""
for i in range(3):
    S = input()
    char_list = list(S)
    x = x + char_list[i]
print(x)
a, b = map(int,input().split())
if a == b :
  print("H")
else:
  print("D")

### FIXED CODE ###

a, b = input().split()
if a == b :
  print("H")
else:
  print("D")
a=list(map(int,input().split()))
a.sort()
if a[0]=5 and a[1]=5 and a[2]=7:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

a=list(map(int,input().split()))
a.sort()
if a[0]==5 and a[1]==5 and a[2]==7:
  print("YES")
else:
  print("NO")
N = int(input())
A = list(map(int, input().split()))
B = []  # 累積和テーブル B[i] = sum(A[:i])
mod = 10**9 + 7
ans = 0

for i in range(N):
    B[i+1] = B[i] + A[i]  # 累積和

for i in range(N):
    sum = (B[N] - B[i+1]) % mod
    ans += A[i] * sum
    ans %= mod

print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = [0] * (N+1)  # 累積和テーブル B[i] = sum(A[:i])
mod = 10**9 + 7
ans = 0

for i in range(N):
    B[i+1] = B[i] + A[i]  # 累積和

for i in range(N):
    sum = (B[N] - B[i+1]) % mod
    ans += A[i] * sum
    ans %= mod

print(int(ans))
n = input()
dish = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dish.append((tmp[0] - tmp[1], tmp[1] - tmp[0], tmp[0], tmp[1]))

point = [0, 0]

player = 0
while len(dish) > 0:
    # print(player.__str__(), player)

    sorted(dish, key=lambda v: dish[player], reverse=True)
    # print(dish[0])
    point[player] += dish.pop(0)[player + 2]
    player = int(not player)
    # print('point', point)

print(point[0] - point[1])


### FIXED CODE ###

n = input()
dishes = []
for i in range(int(n)):
    tmp = [int(each) for each in input().split()]
    dishes.append((abs(tmp[0] + tmp[1]), tmp[0], tmp[1]))

dishes = sorted(dishes, key=lambda x: x[0], reverse=True)

point = [0, 0]
player = 0
while len(dishes) > 0:
    dish = dishes.pop(0)
    point[player] += dish[player + 1]
    player = int(not player)
print(point[0] - point[1])
N=int(input())
A=list(map(int,input().split()))
a=0
s=[]
for i in A:
  if i<a:
    s.append(a-i)
    print(s)
  else:
    a=i
print(sum(s))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=0
s=[]
for i in A:
  if i<a:
    s.append(a-i)
    
  else:
    a=i
print(sum(s))
V = []
for i in range(5):
  V.append(int(input()))
               
k = int(input())
               
d = max(V) = min(V)

if d > k:
  print(":(")
else:
  print("Yay!")


### FIXED CODE ###

V = []
for i in range(5):
  V.append(int(input()))
               
k = int(input())
               
d = max(V) - min(V)

if d > k:
  print(":(")
else:
  print("Yay!")
n,y = map(int, input().split())
 
 
a,b,c = -1,-1,-1
 
for ai in range(n+1):
 
    if ai*1000>y:
        break
 
    if ai * 1000 == y:
        a,b,c = ai,0,0
        break
 
    remain = n-ai
    for bi in range(remain+1):
        ci = remain - bi
        
        if y == ai * 1000 + bi * 5000 + ci * 10000:
            a,b,c = ai,bi,ci
 
print('{} {} {}'.format(c,b,a))
 

n,y = map(int, input().split())


a,b,c = -1,-1,-1

for ai in range(n+1):

    if ai*1000>y:
        break

#    if ai * 1000 == y:
#        a,b,c = ai,0,0
#        break

    remain = n-ai
    for bi in range(remain+1):
        ci = remain - bi
        
        if y == ai * 1000 + bi * 5000 + ci * 10000:
            a,b,c = ai,bi,ci

print('{} {} {}'.format(c,b,a))

提出情報

### FIXED CODE ###



n,y = map(int, input().split())

y //= 1000
a,b,c = -1,-1,-1

for ai in range(n+1):

    if ai*10> y:
        break

    if ai  == y:
        a,b,c = ai,0,0
        break

    remain = n-ai
    for bi in range(remain+1):
        ci = remain - bi
        
        if y == ai *10  + bi * 5 + ci :
            a,b,c = ai,bi,ci


print('{} {} {}'.format(a,b,c))
n,m = map(int, input().split())

l = []
r = []

for i in range(M):
  ln, rn = map(int, input().split())
  l.append(ln)
  r.append(rn)
  
lmax = max(l)
rmin = min(r)

ans = rmin - lmax + 1

print(ans)


### FIXED CODE ###

n, m = map(int, input().split())

l = []
r = []

for i in range(m):
  ln, rn = map(int, input().split())
  l.append(ln)
  r.append(rn)
  
lmax = max(l)
rmin = min(r)


ans = rmin - lmax + 1
if (ans < 0):
  ans = 0

print(ans)
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<limits.h>

#define rep(i,begin,end) for(int i=begin; i<end; i++)
#define revrep(i,begin,end) for(int i=begin; i>end; i--)
#define lld long long int

int cmpAsc(const void* a, const void* b){
    int x = *(int*)a, y = *(int*)b;
    if(x > y){
        return 1;
    }
    if(x < y){
        return -1;
    }
    return 0;
}

int main(){
    int n;
    lld m;
    scanf("%d %lld", &n, &m);
    lld a[n+1];
    a[0] = 0;
    rep(i, 1, n+1){
        scanf("%lld", &a[i]);
    }
    rep(i, 1, n+1){
        a[i] += a[i-1];
        a[i] %= m;
    }
    qsort(a, n+1, sizeof(lld), cmpAsc);
    int cnt = 1, target = -1;
    lld ans = 0;
    rep(i, 0, n+1){
        if(a[i] == target){
            ans += (lld)cnt;
            cnt++;
        }else{
            target = a[i];
            cnt = 1;
        }
    }
    printf("%lld", ans);

    return 0;
}

### FIXED CODE ###

import sys

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

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 0
    a[0] = a[0]%m
    for i in range(1, n):
        a[i] += a[i-1]
        a[i] %= m
    a.sort()
    target = 0
    cnt = 1
    for i in a:
        if i == target:
            ans += cnt
            cnt += 1
        else:
            target = i
            cnt = 1
    print(ans)

if __name__ == "__main__":
    main()
n,k = map(int,input().split())
p = [int(i) for i in input().split()]
p.sort()
for i in range(k) :
    s += p[i]
print(s)

### FIXED CODE ###

n,k = map(int,input().split())
p = [int(i) for i in input().split()]
p.sort()
s = 0
for i in range(k) :
    s += p[i]
print(s)
import math

s=list(input().split('T'))
sn=[]

for i in range(len(s)):
    sn.append(len(s[i]))

x, y = map(int,input().split(' '))
x = x-sn[0]

snx=[]
sny=[]

for i in range(2,len(sn),2):
    snx.append(sn[i])

for i in range(1,len(sn),2):
    sny.append(sn[i])

#X軸判定
xflg = 0
ansx=[]
prex=[0]
for i in range(len(snx)):
    tmpx=set()
    for j in prex:
        tmpx.add(j+snx[i])
        tmpx.add(j-snx[i])
    prex=tmpx

if x in tmpx:
    xflg = 1

#y軸判定
yflg = 0
prey=[0]
for i in range(len(sny)):
    tmpy=set()
    for j in prey:
        tmpy.add(j+sny[i])
        tmpy.add(j-sny[i])
    prey=tmpy

if y in tmpy:
    yflg = 1

if xflg == 1 and yflg == 1:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

import math

s=list(input().split('T'))
sn=[]

for i in range(len(s)):
    sn.append(len(s[i]))

x, y = map(int,input().split(' '))
x = x-sn[0]

snx=[]
sny=[]

for i in range(2,len(sn),2):
    snx.append(sn[i])

for i in range(1,len(sn),2):
    sny.append(sn[i])

#X軸判定
xflg = 0
ansx=[]
prex=[0]
tmpx=[0]
for i in range(len(snx)):
    tmpx=set()
    for j in prex:
        tmpx.add(j+snx[i])
        tmpx.add(j-snx[i])
    prex=tmpx

if x in tmpx:
    xflg = 1

#y軸判定
yflg = 0
prey=[0]
tmpy=[0]
for i in range(len(sny)):
    tmpy=set()
    for j in prey:
        tmpy.add(j+sny[i])
        tmpy.add(j-sny[i])
    prey=tmpy

if y in tmpy:
    yflg = 1

if xflg == 1 and yflg == 1:
    print("Yes")
else:
    print("No")
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = sorted(b, reverse=True)
c = sorted(c, reverse=True)

q = [(a[0]+b[0]+c[0], 0, 0, 0)]
for i in range(min(x*y*z, k)):
  m = q.pop(q.index(max(q, key=lambda x: x[0])))
  print(m[0])
  if m[1] < x-1:
  	next_a = (a[m[1]+1]+b[m[2]]+c[m[3]], m[1]+1, m[2], m[3])
  if m[2] < y-1:
    next_b = (a[m[1]]+b[m[2]+1]+c[m[3]], m[1], m[2]+1, m[3])
  if m[3] < z-1:
    next_c = (a[m[1]]+b[m[2]]+c[m[3]+1], m[1], m[2], m[3]+1)
  if next_a not in q:
    q.append(next_a)
  if next_b not in q:
    q.append(next_b)
  if next_c not in q:
    q.append(next_c)
      

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a = sorted(a, reverse=True)
b = sorted(b, reverse=True)
c = sorted(c, reverse=True)

q = [(a[0]+b[0]+c[0], 0, 0, 0)]
t = []
next_a = (0,0,0,0)
next_b = (0,0,0,0)
next_c = (0,0,0,0)
for i in range(min(x*y*z, k)):
  m = q.pop(q.index(max(q, key=lambda x: x[0])))
  print(m[0])
  if m[1] < x-1:
    next_a = (a[m[1]+1]+b[m[2]]+c[m[3]], m[1]+1, m[2], m[3])
  if m[2] < y-1:
    next_b = (a[m[1]]+b[m[2]+1]+c[m[3]], m[1], m[2]+1, m[3])
  if m[3] < z-1:
    next_c = (a[m[1]]+b[m[2]]+c[m[3]+1], m[1], m[2], m[3]+1)
  if next_a not in t:
    q.append(next_a)
    t.append(next_a)
  if next_b not in t:
    q.append(next_b)
    t.append(next_b)
  if next_c not in t:
    q.append(next_c)
    t.append(next_c)
def zero_origin(s: str):
  return int(s) - 1


class UnionFindTree:
  """Union Find Tree for disjoint-set data structure.

  Args:
    n (int): number of the vertices.
  """
  def __init__(self, n: int):
    self.parent = list(range(n))
    self.rank = [0] * n
    self.size = [1] * n

  def find(self, i: int) -> int:
    if self.parent[i] != i:
      self.parent[i] = self.find(self.parent[i])
    return self.parent[i]

  def unite(self, i: int, j: int):
    ri = self.find(i)
    rj = self.find(j)
    size = self.size[ri] + self.size[rj]
    self.size[ri] = size
    self.size[rj] = size
    if ri != rj:
      if self.rank[ri] < self.rank[rj]:
        self.parent[ri] = rj
      else:
        self.parent[rj] = ri
        if self.rank[ri] == self.rank[rj]:
          self.rank[ri] += 1

  def is_same(self, i: int, j: int) -> bool:
    return self.find(i) == self.find(j)


n, m = map(int, input().split())
uft = UnionFindTree(n)
for _ in range(m):
  a, b = map(zero_origin, input().split())
  uft.unite(a, b)
print(max(utf.size))

### FIXED CODE ###

def zero_origin(s: str):
  return int(s) - 1


class UnionFindTree:
  """Union Find Tree for disjoint-set data structure.

  Args:
    n (int): number of the vertices.
  """
  def __init__(self, n: int):
    self.parent = list(range(n))
    self.rank = [0] * n
    self.size = [1] * n

  def find(self, i: int) -> int:
    if self.parent[i] != i:
      self.parent[i] = self.find(self.parent[i])
    return self.parent[i]

  def unite(self, i: int, j: int):
    ri = self.find(i)
    rj = self.find(j)
    if ri != rj:
      if self.rank[ri] < self.rank[rj]:
        self.parent[ri] = rj
        self.size[rj] += self.size[ri]
      else:
        self.parent[rj] = ri
        self.size[ri] += self.size[rj]
        if self.rank[ri] == self.rank[rj]:
          self.rank[ri] += 1

  def is_same(self, i: int, j: int) -> bool:
    return self.find(i) == self.find(j)


n, m = map(int, input().split())
uft = UnionFindTree(n)
for _ in range(m):
  a, b = map(zero_origin, input().split())
  uft.unite(a, b)
print(max(uft.size))
S = input()
ans = 0
for i in S:
  if i == "+":
    ans++
  else:
    ans--
print(ans)


### FIXED CODE ###

S = input()
ans = 0
for i in S:
  if i == "+":
    ans += 1
  else:
    ans -= 1
print(ans)
c1 = input()
c2 = input()

print("Yes" if c1 = c2[::-1] else "No")

### FIXED CODE ###

c1 = input()
c2 = input()

print("YES" if c1 == c2[::-1] else "NO")
def menseki(a, b):
    return a * b - (1 * b + 1 * a - 1)

if __name__ == '__main__':
    la = int(input())
    lb = int(input())

    print(menseki(la, lb))


### FIXED CODE ###

def menseki(a, b):
    return a * b - (1 * b + 1 * a - 1)

if __name__ == '__main__':
    la, lb = map(int, input().split())
    print(menseki(la, lb))
import sys
sys.setrecursionlimit(10000000000)

N = int(input())
H = list(list(map(int,input().split())) for _ in range(N))
#sub problem: max cost from 0 to ith day
def rec(i, choice):
  if i == len(H):
    return 0
  return max(H[i][j] + rec(i+1,j) for j in range(3) if j != choice)
print(max(rec(0, j) for j in range(3)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
 
N = int(input())
H = list(list(map(int,input().split())) for _ in range(N))
#sub problem: max cost from 0 to ith day
memo = {}
def rec(i, choice):
  if (i, choice) in memo:
    return memo[(i, choice)]
  if i == len(H):
    return 0
  m = max(H[i][j] + rec(i+1,j) for j in range(3) if j != choice)
  memo[(i, choice)] = m
  return m
print(max(rec(0, j) for j in range(3)))
N=int(input())
A=list(int, input().split())
counter=[]
for num in range(N):
  counter.append(0)
for num in range(N):
  while A[num]%2==0:
    A[num]=A[num]/2
    counter[num]+=1
print(sum(counter))
  

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
counter=[]
for num in range(len(A)):
  counter.append(0)
for num in range(len(A)):
  while A[num]%2==0:
    A[num]=A[num]/2
    counter[num]+=1
print(sum(counter))
import math

while True :

x = int(input()) 

  if x == 0 :
    break 

  else :
    sum = 0 
    n=floor(log(x,10))
    sum = floor(x/pow(10,n))
    for i in reversed(xrange(n+1)):
      sum = sum + floor((x%pow(10,i))/pow(10,i-1))

  print(sum)

### FIXED CODE ###

while True :
  x = input()
  if x == '0' :
    break 

  else:
   sum = 0 
   for i  in range(len(x)) :  
    sum += int(x[i])

  print(sum)
a = 20
b = int(input())
if a % b == 0 and a % b != 0:
    print("even")
else:
    print("odd")

### FIXED CODE ###

a, b = map(int, input().split())
if (a*b) % 2:
  print('Odd')
else:
  print('Even')
n, m = map(int, input().split())
b = [False]*(n+1)
dp = [None]*(n+1)
M = 10**9+7
dp[0] = 1
dp[1] = 1

def up(x):
    if b[x] == True:
        return 0
    res = 0
    if dp[x-1] == None:
        dp[x-1] = up(x-1)
    res += dp[x-1]
    if dp[x-2] == None:
        dp[x-2] = up(x-2)
    res += dp[x-2]
    return (res%M)

for i in range(m):
    a = int(input())
    b[a] = True
if b[1] == True:
    dp[1] = 0

print(up(n))

### FIXED CODE ###

n, m = map(int, input().split())
b = [False]*(n+2)
for _ in range(m):
    i = int(input())
    b[i] = True
M = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    if b[i] == False:
        dp[i] = (dp[i-1] + dp[i-2])%M
print(dp[n])
n = int(input())
a = []
for i in range(1, n+1):
  while True:
    if i % 2 != 0:
      break
    i = i // 2
    c += 1
  a.append(c)
print(a.index(max(a)) + 1)

### FIXED CODE ###

n = int(input())
a = []
for i in range(1, n+1):
  c = 0
  while True:
    if i % 2 != 0:
      break
    i = i // 2
    c += 1
  a.append(c)
print(a.index(max(a)) + 1)
n,r=map(int,input());
print(r+100*min(10-n,0));

### FIXED CODE ###

n,r=map(int,input().split());
print(r+100*max(10-n,0));
#!/usr/bin/env python
import math

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

(a, b) = [int(e) for e in input().split(" ")][:2]
print(int(lcm(a, b)))


### FIXED CODE ###

import math
from fractions import gcd

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

(a, b) = [int(e) for e in input().split(" ")[:2]]
print(int(lcm(a, b)))
n, m = [int(i) for i in input().split()]

matrix = []
for ni in range(n):
    matrix.append([int(a) for a in input().split()])

vector = []
for ni in range(n):
    vector.append(int(input()))

b = []
for ni in range(n):
    sum = 0
    for mi in range(m):
        sum += matrix[ni][mi] * vector[mi]

    print(sum)

### FIXED CODE ###

n, m = [int(i) for i in input().split()]

matrix = []
for ni in range(n):
    matrix.append([int(a) for a in input().split()])

vector = []
for mi in range(m):
    vector.append(int(input()))

for ni in range(n):
    sum = 0
    for mi in range(m):
        sum += matrix[ni][mi] * vector[mi]

    print(sum)
def perm(n, k, mod):
    ret = 1
    for i in range(k):
        ret *= n - i
        ret %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
    if K <= 2:
        if N <= K:
            print(perm(K, N, MOD))
        else:
            print(0)
        return
    perm_k1 = [perm(K - 1, k, MOD) for k in range(K)]
    perm_k2 = [perm(K - 2, k, MOD) for k in range(K - 1)]

    def dfs(n=0, p=-1):
        # node, parentの色を固定した時の色の塗り方
        children = [c for c in adj[n] if c != p]
        if len(children) == 0:
            return 1
        n_colors = K - 2 if n != 0 else K - 1
        if n_colors < len(children):
            return 0
        ret = perm_k2[len(children)] if n != 0 else perm_k1[len(children)]
        for c in children:
            ret *= dfs(c, n)
            ret %= MOD
        return ret

    print((K * dfs()) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    adj = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split(' ')))
        adj[a].append(b)
        adj[b].append(a)
    if K <= 2:
        if N <= K:
            p = 1
            for n in range(N):
                p *= K - n
            print(p % MOD)
        else:
            print(0)
        return
    p = 1
    perm_k1 = [0 for _ in range(K)]
    for k in range(K):
        perm_k1[k] = p
        p *= K - 1 - k
        p %= MOD
    perm_k2 = [0 for _ in range(K - 1)]
    p = 1
    for k in range(K - 1):
        perm_k2[k] = p
        p *= K - 2 - k
        p %= MOD

    def dfs(n=0, p=-1):
        # node, parentの色を固定した時の色の塗り方
        children = [c for c in adj[n] if c != p]
        if len(children) == 0:
            return 1
        n_colors = K - 2 if n != 0 else K - 1
        if n_colors < len(children):
            return 0
        ret = perm_k2[len(children)] if n != 0 else perm_k1[len(children)]
        for c in children:
            ret *= dfs(c, n)
            ret %= MOD
        return ret

    print((K * dfs()) % MOD)


if __name__ == '__main__':
    main()
N = [int(a) for a in input().split()]
N.sort()
K = int(input())
print(A[0] + A[1] + A[2] * 2 ** K)

### FIXED CODE ###

A = [int(a) for a in input().split()]
A.sort()
K = int(input())
print(A[0] + A[1] + A[2] * 2 ** K)
l=list(map(int,input().split()))
d=list(map(int,input().split()))
d_bar=[]
for m in range(10):
    if m not in d:
        d_bar.append(m) 
d_bar.sort()
a=[]
p=0
n_int=[int(k) for k in str(l[0])]
for i in range(len(n_int)):
    a.append(10)
    for j in range(len(d_bar)):
        if n_int[-i-1]==d_bar[j]:
            a.pop(i)
            a.append(d_bar[j+p])
            p=0
            break
        elif n_int[-i-1]<d_bar[j]:
            a.pop(i)
            a.append(d_bar[j])
            p=0
            break
    if a[i]==10:
        a.pop(i)
        a.append(d_bar[0])
        p=1
b=''
for q in range(len(n_int)):
    b=b+str(a[-q-1]) 
print(int(b))

### FIXED CODE ###

l=list(map(int,input().split()))
d=list(map(int,input().split()))
u={i for i in range(10)}
d_bar=u-set(d)
d_bar={str(i) for i in d_bar}
n=l[0]
n_set=set(str(n))
while True:
    if n_set<=d_bar:
        print(n)
        break
    n=n+1
    n_set=set(str(n))
from ctypes import c_longlong as ll

n = ll(input(""))
m = ll(input(""))
n= n % m
print(min(n, m-n))

### FIXED CODE ###

import numpy

n, m = input().split()
n = numpy.int64(n)
m = numpy.int64(m)
n = n % m
print(min(n, m-n))
N = int(input())
A = list(map(int, input().split()))

import sympy

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

Ai = []
count = 0
for i in range(N):
    Ai = make_divisors(A[i])
    for j in range(len(Ai)):
        if Ai[j] in A and Ai[j] != A[i]:
            count += 1
            break

print(N - count)

### FIXED CODE ###

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

for i in range(5):
    if x[i] == 0:
        print(i+1)