Harryxun/stf_run huggingface dataset:
import numpy as np
import fractions
import sys

input = sys.stdin.readline


def primesfrom2to(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = np.ones(n // 3 + (n % 6 == 2), dtype=np.bool)
    for i in range(1, int(n ** 0.5) // 3 + 1):
        if sieve[i]:
            k = 3 * i + 1 | 1
            sieve[k * k // 3 :: 2 * k] = False
            sieve[k * (k - 2 * (i & 1) + 4) // 3 :: 2 * k] = False
    return np.r_[1, 2, 3, ((3 * np.nonzero(sieve)[0][1:] + 1) | 1)]


def main():
    a, b = list(map(int, input().split()))
    # 10 ** 12
    # 愚直だと公約数を求めるだけでも時間切れする
    # 互いに素な公約数がほぼ素数などでは？
    g = fractions.gcd(a, b)
    print(len([i for i in primesfrom2to(g) if g % i == 0]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

import fractions
import sys

input = sys.stdin.readline


def factorization(n):
    primes = []
    while n % 2 == 0:
        primes.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            primes.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        primes.append(n)
    return primes


def main():
    a, b = list(map(int, input().split()))

    # 素因数分解
    g = fractions.gcd(a, b)
    print(len(set(factorization(g))) + 1)


if __name__ == "__main__":
    main()
n=int(input())
l=[0]*n
for i in range(n):
    l[i]=int(input())

vi=[0]*n
vi[0]=1
ans=1
st=l[0]
f=0
while vi[1]==0:
    vi[st]+=1
    if vi[st]>1:
        f=1
        break
    st=l[st-1]
    ans+=1
if f==0:
    print(ans)
else:
    print(-1)
    
    
  
  
    

### FIXED CODE ###

n=int(input())
l=[0]*n
for i in range(n):
    l[i]=int(input())

vi=[0]*n
vi[0]=1
ans=0
st=l[0]
f=0
while vi[1]==0:
    vi[st-1]+=1
    if vi[st-1]>1:
        f=1
        break
    st=l[st-1]
    ans+=1
if f==0:
    print(ans)
else:
    print(-1)
from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

H,W=[int(i) for i in input().split()]
C=[input() for _ in range(H)]
C=[list(i) for i in C] 

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]
stack = deque([[0, 0, 0]])
visited_list[0][0] = 0

w_cnt=0
for c in C: w_cnt += c.count(".")

def seek(, visited_list, stack):
    global ans
    flag = 0
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            flag = 1
            continue
        for j, k in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  [new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt + 1:
                visited_list[new_h][new_w] = cnt + 1
                stack.append([new_h, new_w, cnt+1])
    if flag: 
        ans = w_cnt-(ans+1)
        return ans
    else: return -1

print(seek(C, visited_list, stack))

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

H,W=[int(i) for i in input().split()]
C=[input() for _ in range(H)]
C=[list(i) for i in C] 

ans = 10**9

visited_list = [[10**9]*W for _ in range(H)]
stack = deque([[0, 0, 0]])
visited_list[0][0] = 0

w_cnt=0
for c in C: w_cnt += c.count(".")

def dfs(town, visited_list, stack):
    global ans
    flag = 0
    while len(stack) > 0:
        h, w, cnt = stack.pop()
        if h == H-1 and w == W-1 and ans > cnt:
            ans = cnt
            flag = 1
            continue
        for j, k in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if  town[new_h][new_w] != "#" and visited_list[new_h][new_w] > cnt + 1:
                visited_list[new_h][new_w] = cnt + 1
                stack.append([new_h, new_w, cnt+1])
    if flag: 
        ans = w_cnt-(ans+1)
        return ans
    else: return -1

print(dfs(C, visited_list, stack))
n = int(input())
if n%9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import math
z,x,t=map(int, input().split())

ans =math.ceil(z/x)*t
print(ans)
s = input()
a = 0
for _ in s:
    a += 1 
if  a != 4:
    print('No')
elif s[0] == s[1] and s[2] == s[3] and s[0] != s[2]:
    print('Yes')
elif s[0] == s[2] and s[1] == s[3] and s[0] != s[1]:
    print('Yes')
elif s[0] == s[3] and s[1] == s[2] and a[0] != s[1]:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

s = sorted(input())
if (s[0] == s[1]) and (s[2] == s[3]) and (s[0] != s[2]):
        print('Yes')
elif (s[0] == s[2]) and (s[1] == s[3]) and (s[0] != s[1]):
        print('Yse')
elif (s[0] == s[3]) and (s[1] == s[2]) and (s[0] != s[1]):
        print('Yes')
else:
    print('No')
n = int(input())
adjacent_list = [[] for i in range(n+1)]
data = []
edgedata = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data.append([a,b])
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#adjacent_list = sorted(adjacent_list, key = lambda x:len(x),reverse = True)
max_node = 0
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > max_node:
        max_node = i
k = len(adjacent_list[max_node])
def dfs(node, num):
    global edgedata
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    color_list = [i for i in range(1,k+1) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        if i not in finished:
            s = min(node, i)
            t = max(node, i)
            edgedata[s][t] = color_list[c_i]
            dfs(i, color_list[c_i])
            c_i += 1
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[i[0]][i[1]])
#output k


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
#隣接リスト
adjacent_list = [[] for i in range(n+1)]
#入力されたデータを保存しておくやつ
data = [None] * (n - 1)
#最終的に色を入れておくやつ。
#edgedata[(1,2)] => 1->2の辺の色を入れておく
edgedata = {}
for i in range(n-1):
    a, b = list(map(int, input().split()))
    data[i] = [a, b]
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
#つながってるノードが一番多いやつを保存しておく
max_node = 0
#探索が終わったやつを入れる
finished = set()
for i in range(1,n):
    if len(adjacent_list[i]) > len(adjacent_list[max_node]):
        max_node = i
#kには色の種類を入れる
k = len(adjacent_list[max_node])
#print("k => {}".format(k))
def dfs(node, num):
    #隣接リストの中身を、つながってるノード順にソート
    node_list = sorted(adjacent_list[node], key = lambda x:len(adjacent_list[x]))
    #さっきつかったいろは使わないようにする
    color_list = [i for i in range(1,len(node_list) + 2) if i != num]
    c_i = 0
    finished.add(node)
    for i in node_list:
        #まだ見てなかったら、dfsを掛ける
        if i not in finished:
            #小さいほうから大きいほうに文字を並べ、ハッシュに値を保存
            #print("{}".format(color_list))
            #print("c_i =>{}  node =>{}".format(c_i,node))
            edgedata[(min(node, i), max(node, i))] = color_list[c_i]
            #color_list[c_i]は使ったので、使った色として引数で渡す。
            dfs(i, color_list[c_i])
            #この色は使ったから、一個ずらす
            c_i += 1
#一番のノードを根とし、dfsをかける
dfs(k,-1)
print(k)
for i in data:
    print(edgedata[tuple(i)])
#output k
n = int(input())
a = list(map(int,input().split()))

total = sum(a)
s = 0
i = 0
ans = total + 1
while True:
    s += a[i]
    total -= a[i]
    ans = min(ans, abs(s - total))
    i += 1
print(ans)

### FIXED CODE ###

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

s = a[0]
t = sum(a) - a[0]

i = 0
ans = abs(s - t)
for i in range(1, n-1):
    s += a[i]
    t -= a[i]
    ans = min(ans, abs(s - t))
    i += 1
print(ans)
import numpy as np

n, m = map(int, input().split())
hlist = np.array(list(map(int, input().split()))).astype(np.int64)
ab = [list(map(int, input().split())) for _ in range(m)]
connect = np.zeros((n,n)).astype(np.int64)

### FIXED CODE ###

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

maxh = [0]*n
for a, b in ab:
  maxh[a-1] = max(maxh[a-1], hlist[b-1])
  maxh[b-1] = max(maxh[b-1], hlist[a-1])
ans = 0
for i in range(n):
  if maxh[i] < hlist[i]:
    ans += 1
print(ans)
#include<iostream>
#include<vector>
using namespace std;

int main(){
  int n,m;cin >> n >> m;
  vector<int> x;
  bool f=false;
  for(int i=0;i<m;i++){
    int a,b;cin >> a >>b;
    if(a==1){
      if(find(x.begin(),x.end(),b)!=x.end()){
        cout << "POSSIBLE" << endl;f=true;break;
      }else{
        x.push_back(b);
      }
    }
    if(b==n){
      if(find(x.begin(),x.end(),a)!=x.end()){
        cout << "POSSIBLE" << endl;f=true;break;
      }else{
        x.push_back(a);
      }
    }
  }
  if(!f){cout << "IMPOSSIBLE" << endl;}

}


### FIXED CODE ###

n,m=map(int,input().split())
x=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        x.append(b)
    if b==n:
        x.append(a)
l=len(x)
if len(set(x))==l:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
a, b, k = map(int, input().split())
for i in range(1, max(a, b)):
    if a % i == 0 and b % i == 0:
        counter += 1
        ret = i
        if counter == k:
            break

# 出力
print("{}".format(int(ret)))

### FIXED CODE ###

a, b, k = map(int, input().split())
counter = 0
for i in range(100, 0, -1):
    if a % i == 0 and b % i == 0:
        counter += 1
        if counter == k:
            print("{}".format(int(i)))
            break
n,x,m = map(int,input().split())
mod = m
ans = 0
bit = [-1 for i in range(m)]
cycle = False
for i in range(n):
    if i == 0 :
        a = x
        bit[a] = i
        ans += a
    else:
        a = (a**2)% mod
        if bit[a] != -1:
            cy_st = bit[a]
            cy_fi = i -1
            cycle = True
            break
        else:
            bit[a] = i
            ans += a

if cycle:
    ans2 = 0
    for j in range(cy_st):
        if j == 0 :
            b = x
            ans2 += b
        else:
            b = (a**2)% mod
            ans2 += b
    cy_num = ans - ans2
    cy_repe = (n-cy_st) // (cy_fi - cy_st + 1)
    ans3 = cy_num * cy_repe
    cy_amari = (n-cy_st) % (cy_fi - cy_st + 1)
    for i in range(cy_amari):
        b = (b**2)% mod
        ans3 += b

    print(ans2+ans3)
else:
    print(ans)


### FIXED CODE ###

n,x,m = map(int,input().split())
mod = m
ans = 0
bit = [-1 for i in range(m)]
cycle = False
for i in range(n):
    if i == 0 :
        a = x
        bit[a] = i
        ans += a
    else:
        a = (a**2)% mod
        if bit[a] != -1:
            cy_st = bit[a]
            cy_fi = i -1
            cycle = True
            break
        else:
            bit[a] = i
            ans += a

if cycle:
    ans2 = 0
    b =  -1
    for j in range(cy_st):
        if j == 0 :
            b = x
            ans2 += b
        else:
            b = (b**2)% mod
            ans2 += b
    cy_num = ans - ans2
    cy_repe = (n-cy_st) // (cy_fi - cy_st + 1)
    ans3 = cy_num * cy_repe
    cy_amari = (n-cy_st) % (cy_fi - cy_st + 1)
    
    if b == -1:
        for j in range(cy_amari):
            if j == 0 :
                b = x
                ans3 += b
            else:
                b = (b**2)% mod
                ans3 += b
        
    else:
        for i in range(cy_amari):
            b = (b**2)% mod
            ans3 += b

    print(ans2+ans3)
else:
    print(ans)
MOD = 1000000007

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

C.sort(reverse=True)

ans = 0

for i in range(N):
    ans += C[i]*(2+i)*pow(2,N-2,MOD)*pow(2,N,MOD)
    ans %= MOD

print(ans)

### FIXED CODE ###

MOD = 1000000007

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

C.sort(reverse=True)

ans = 0

if N > 1:
    for i in range(N):
        ans += C[i]*(2+i)*pow(2,N-2,MOD)*pow(2,N,MOD)
        ans %= MOD
else:
    ans = 2*C[0]%MOD

print(ans)
A = int(input())
B = int(input())

a = str(A)
b = str(B)

count = 0
for i in range (A,B,1):
    I = str(i)
    if int(I[-1]) == int(I[-5]) and int(I[-2]) == int(I[-4]):
        count = count + 1
    else :
        pass

print(count)

### FIXED CODE ###

i = list(map(int, input().split()))
A = i[0]
B = i[1]

count = 0
for i in range (A,B+1,1):
    I = str(i)
    if int(I[-1]) == int(I[-5]) and int(I[-2]) == int(I[-4]):
        count = count + 1
    else :
        pass

print(count)
a,b,c,d = map(int, input())
if b < c or d < a:
    ans = 0
else:
    ans = min(abs(c-b), abs(d-a))
print(ans)


### FIXED CODE ###

a,b,c,d = map(int, input().split())
if b < c or d < a:
    ans = 0
else:
    ans = min(abs(c-b), abs(d-a), abs(b-a), abs(d-c))
print(ans)
import itertools
s=range(0,10)
chk=list(itertools.product(s,repeat=4))
for j in sys.stdin:
    ans=0
    for k in chk:
        if sum(k)==int(j):
            ans+=1
    print ans

### FIXED CODE ###

import itertools
import sys
s=range(0,10)
chk=list(itertools.product(s,repeat=4))
for j in sys.stdin:
    ans=0
    for k in chk:
        if sum(k)==int(j):
            ans+=1
    print ans
n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
def f(L):
    if A[L[-1]-1] not in L:
        L.append(A[L[-1]-1])
        return f(L)
    else:
        return L
P = f(L)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j
print(P)
if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, k = map(int, input().split())
A = list(map(int, input().split()))
L = [1]
S = {1}

def f(L, S):
    last = L[-1]-1
    if A[last] not in S:
        L.append(A[last])
        S |= {A[last]}
        return f(L, S)
    else:
        return L
P = f(L, S)
a = A[P[-1]-1]
j = P.index(a)
r = len(P)
l = r - j

if k+1 <= j:
    print(P[k])
else:
    print(P[j+(k-j)%l])
n=input()
a=list(map(int,input().split()))
a.sort()
print(a[-1]-a[0])

### FIXED CODE ###

r,g,b=map(int,input().split())
x=r*100+g*10+b
if x%4==0:
    print("YES")
else:
    print("NO")
X, Y, A, B, C = map(int,input().split()) 
P = [list(map(int,input().split())) for i in range(3)]
Red = sorted(P[0], reverse=True)
Green = sorted(P[1], reverse=True)
Trans = sorted(P[2], reverse=True)

pre_max = sum(Red[:X]) + sum(Green[:Y])
Red = Red[:X]
Green = Green[:Y]
for i in range (C):
  maxo = pre_max
  if (Trans[i] > Red[-1+i]):
    maxo= pre_max + Trans[i] - Red[-1+i]
for i in range (C):
  if (Trans[i] > Green[-1+i]):
    maxo = pre_max + Trans[i] - Green[-1+i]
    
print(maxo)

### FIXED CODE ###

S = input()
if(S[2] == S[3] and S[4]==S[5] ):
	print("Yes")
else :
	print("No")
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b_list = []
for i in range(1,n+1):
    if i == a_list[i]:
        b_list[i] += 1
    else:
        b_list[i] = 1
b_list.sort(reverse = True)
f = sum(b_list[:k:])
print(n-f)


### FIXED CODE ###

import collections
n, k = map(int, input().split())
a_list = list(map(int, input().split()))
b = collections.Counter(a_list)
d = b.most_common()[k:]
sum = 0
for i in d:
    sum += i[1]
print(sum)
from functools import reduce
    n = int(input())
    tab = [int(n) for n in input().split()]
    if 0 in tab:
      print("0")
    res = reduce(lambda x, y: x*y, tab)
    if res > 1000000000000000000:
      print("-1")
    else:
      print(res)

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod *= a
		if prod > 1000000000000000000:
			print(-1)
			return
	print(prod)
main()
from sys import exit

n=int(input())
x=[0]*n
y=[0]*n
h=[0]*n

for i in range(n):
	xx,yy,hh=map(int,input().split())
	x[i]=xx
	y[i]=yy
	h[i]=hh
	
hres=0

if n==1:
	print(xx,yy,hh)
	exit()
else:
	for cx in range(101):
		for cy in range(101):
			cnt=0
			h2=h[0]+abs(x[0]-cx)+abs(y[0]-cy)
			for i in range(1,n):
				h1=h[i]+abs(x[i]-cx)+abs(y[i]-cy)
				if h2!=h1:
					cnt=1
			if cnt==0 and h1>hres:
				hres=h1
				xres=cx
				yres=cy
				
print(xres,yres,hres)

### FIXED CODE ###

from sys import exit

def ht(cx,cy,x,y,h):
	return h+abs(x-cx)+abs(y-cy)

n=int(input())			#高々100なのでほとんどが高さ0っていう状況はない
xyh=[0]*n

for i in range(n):
	x,y,h=map(int,input().split())
	xyh[i]=[x,y,h]
xyh.sort(key=lambda x:x[2],reverse=True)			#h=0を選択してしまうことを避ける

for cx in range(101):
	for cy in range(101):
		H=ht(cx,cy,xyh[0][0],xyh[0][1],xyh[0][2])
		for i in range(1,n):
			if max(H-abs(xyh[i][0]-cx)-abs(xyh[i][1]-cy),0)!=xyh[i][2]:			#H=ht(このfor文で選択した座標)にすると、高さ0の場合に合わなくなる
				break
			
		else:			#直前のifが行われなければ、という意味。forの外における
			print(cx,cy,H)
			exit()
# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def solve():
    N = int(input())
    A = [0, *map(int, input().split())]
    B = [0, *map(int, input().split())]

    dp = [[0,0,0,0] for _ in range(N+max(A+B)+5)]
    X, Y = A, B
    for i,w in product(range(1,4), range(1,N+1)):
        dp[w][i] = max(dp[w-X[i]*j][i-1]+Y[i]*j for j in range(0,w//X[i]+1) if w>=X[i]*j) if w>=X[i] else dp[w][i-1]
    N = dp[N][3]
    dp = [[0,0,0,0] for _ in range(N+1)]
    X, Y = B, A
    for i,w in product(range(1,4), range(1,N+1)):
        dp[w][i] = max(dp[w-X[i]*j][i-1]+Y[i]*j for j in range(0,w//X[i]+1)  if w>=X[i]*j) if w>=X[i] else dp[w][i-1]
    res = dp[N][3]
    return res





    return res
if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

if __name__ == '__main__':
    print(solve())
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = 10**9+7

def comb(n, r):
    if 2*r > n: comb(n, n-r)
    return fac[n] * inv[r] * inv[n-r] % mod

def dfs(v, Pa=-1):
    for u in to[v]:
        if u == Pa: continue
        dfs(u, v)
        size[v] += size[u]
        dp[v] *= dp[u] % mod
        dp[v] *= comb(size[v], size[u]) % mod
    size[v] += 1

def bfs(v, Pa=-1, P_val=1, P_sz=0):
    ans[v] = P_val * dp[v] * comb(n-1, P_sz) % mod
    for u in to[v]:
        if u == Pa: continue
        val = ans[v] * INV(dp[u]*comb(n-1, size[u])) % mod
        bfs(u, v, val, n-size[u])

n = int(input())
to = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)

fac = [1] * (n+1)
inv = [1] * (n+1)

for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
INV = lambda x: pow(x, mod - 2, mod)
inv[n] = INV(fac[n])
for i in range(n-1, 1, -1):
    inv[i] = inv[i+1] * (i+1) % mod

dp = [1] * n
size = [0] * n
ans = [0] * n

dfs(0)
bfs(0)
print(*ans, sep='\n')

### FIXED CODE ###

import sys

def solve():
    input = lambda: sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10 ** 7)
    mod = 10 ** 9 + 7

    def comb(n, r):
        if r > n: return 0
        return fac[n] * inv[r] * inv[n - r] % mod

    def dfs(v, Pa=-1):
        for u in to[v]:
            if u == Pa: continue
            dfs(u, v)
            size[v] += size[u]
            dp[v] *= dp[u] % mod
            dp[v] *= inv[size[u]] % mod
        dp[v] *= fac[size[v]] % mod
        size[v] += 1

    def bfs(v, Pa=-1, P_val=1, P_sz=0):
        ans[v] = P_val * dp[v] * comb(n - 1, P_sz) % mod
        for u in to[v]:
            if u == Pa: continue
            val = ans[v] * INV(dp[u] * comb(n - 1, size[u])) % mod
            bfs(u, v, val, n - size[u])

    n = int(input())
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        to[a].append(b)
        to[b].append(a)

    fac = [1] * (n + 2)
    inv = [1] * (n + 2)

    for i in range(2, n + 1):
        fac[i] = fac[i - 1] * i % mod
    INV = lambda x: pow(x, mod - 2, mod)
    inv[n] = INV(fac[n])
    for i in range(n - 1, 1, -1):
        inv[i] = inv[i + 1] * (i + 1) % mod

    dp = [1] * n
    size = [0] * n
    ans = [0] * n

    dfs(0)
    bfs(0)
    print(*ans, sep='\n')

if __name__ == '__main__':
    solve()
def search(i,s):
	if i == n-1:
		li = []
		s = "".join(s)
		li = list(map(int,s.split("+")))
		total.append(sum(li))
		return

	else:
		search(i+1,s)

		_s = s[:-(n-i)+1] + ["+"] + s[-(n-i)+1:]
		search(i+1,_s)

search(0,s)
print(sum(total))

### FIXED CODE ###

s = list(input())
total = []
n = len(s)

def search(i,s):
	if i == n-1:
		li = []
		s = "".join(s)
		li = list(map(int,s.split("+")))
		total.append(sum(li))
		return

	else:
		search(i+1,s)

		_s = s[:-(n-i)+1] + ["+"] + s[-(n-i)+1:]
		search(i+1,_s)

search(0,s)
print(sum(total))
from collections import Counter
n=int(input())
v=list(map(int,input().split()))

A=v[0::2]
B=v[1::2]
a=len(A)
b=len(B)

#print(Counter(A).most_common()[0][0])
#print(Counter(B).most_common()[0][0])

if Counter(A).most_common()[0][0] !=Counter(B).most_common()[0][0]:
    s=Counter(A).most_common()[0][1]
    t=Counter(B).most_common()[0][1]
    print( (a-s)+(b-t))
else:
    o=Counter(A).most_common()[1][1]
    p=Counter(B).most_common()[0][1]
    r= (a-o)+(b-p)
    w=Counter(A).most_common()[0][1]
    x=Counter(B).most_common()[1][1]
    s= (a-w)+(b-x)
    print(min( r, s))


### FIXED CODE ###

from collections import Counter
n=int(input())
v=list(map(int,input().split()))

A=v[0::2]
B=v[1::2]
a=len(A)
b=len(B)

#print(Counter(A).most_common()[0][0])
#print(Counter(B).most_common()[0][0])

if Counter(A).most_common()[0][0] !=Counter(B).most_common()[0][0]:
    s=Counter(A).most_common()[0][1]
    t=Counter(B).most_common()[0][1]
    print( (a-s)+(b-t))
else:
  r=a
  s=b
  if Counter(A).most_common()[0][1]<a:
    o=Counter(A).most_common()[1][1]
    p=Counter(B).most_common()[0][1]
    r= (a-o)+(b-p)
  if Counter(B).most_common()[0][1]<b:
    w=Counter(A).most_common()[0][1]
    x=Counter(B).most_common()[1][1]
    s= (a-w)+(b-x)
  print(min( r, s))
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

count = [0 for i in range(10**5)]

for a_i in A:
    count[a_i] += 1

for i in range(Q):
    B, C = map(int, input().split())
    tmp = count[B]
    count[B] = 0
    count[C] += tmp
    ans = 0
    for j in range(10**5):
        ans += j*count[j]
    print(ans)


### FIXED CODE ###

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

count = [0 for i in range(10**5+1)]

for a_i in A:
    count[a_i] += 1

bef_ans = 0
for i in range(Q):
    B, C = map(int, input().split())
    tmp = count[B]
    count[B] = 0
    count[C] += tmp
    ans = 0
    if i == 0:
        for j in range(10**5+1):
            ans += j*count[j]
    else:
        ans = bef_ans - B*tmp + C*tmp
    print(ans)
    bef_ans = ans
n = int(input())
x = [int(i) for i in input().split()]
for i in range(n):
    tmp = list(x)
    tmp[i] *= -1
    tmp.sort()
    median = int(n/2)
    print(tmp[median])
    


### FIXED CODE ###

ipt = [int(i) for i in input().split()]
a = ipt[0]
b = ipt[1]
x = ipt[2]

if a <= x and x <= a+b:
    print("YES")
else:
    print("NO")
n=input()
total=0
for i in len(n):
    total=total+int(n[i])
if n%total==0:
    print('Yes')
else:
    print('No')
    




### FIXED CODE ###

n=input()
total=0
for i in range(len(n)):
    total=total+int(n[i])
if int(n)%total==0:
    print('Yes')
else:
    print('No')