Harryxun/stf_run huggingface dataset:
import math

a,b,c,d=map(int,input().split())
C=b//c-((a-1)//c)
D=b//d-((a-1)//d)
g=math.gcd(c,d)
l=c*d/g
E=b//l-((a-1)//l)
print(int(b-a+1-C-D+E))

### FIXED CODE ###

import fractions

a,b,c,d=map(int,input().split())
g=int(fractions.gcd(c,d))
l=int((c*d)/g)

print(b-a+1-int(b//c)+int((a-1)//c)-int(b//d)+int((a-1)//d)+int(b//l)-int((a-1)//l))
X = int(input())
X = range(-40 < 40)
if X > 30:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

X = int(input())
if X >= 30:
    print("Yes")
else:
    print("No")
from itertools import *
from collections import *
from bisect import *


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

ruiA=[0 for i in range(N+1)]
for i in range(0,N):
    ruiA[i+1]=ruiA[i]+A[i]


nlst=[]

for i in range(len(ruiA)-1):
    for m in range(i+1,len(ruiA)):
        nlst.append(ruiA[m]-ruiA[i])
nlst.sort(reverse=True)

lenbin=31
for i in range(len(nlst)):
    a=bin(nlst[i])[2:]
    nlst[i]=[0 for i in range(lenbin-len(a))]+list(map(int,list(a)))
    #print(nlst[i])
lenbinst=0

#print(nlst)
while lenbinst<lenbin:
    idx=-1
    count=0
    for m in range(len(nlst)):
        if nlst[m][lenbinst]==1:
            count+=1
    if count>=K:
        idx=lenbinst

    if idx==-1:
        pass
    else:
        nlst=[i for i in nlst if i[idx]==1]
    lenbinst+=1
valuelst=[0 for i in range(lenbin)]

for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1

for i in range(lenbin):
    if valuelst[i]>=K:
        newlst=[i for i in nlst if i[idx]==1]
        if len(newlst)>=K:
            nlst=newlst

valuelst=[0 for i in range(lenbin)]
for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1
value=0
for i in range(lenbin):
    if valuelst[i]>=K:
        value+=2**i
print(value)


### FIXED CODE ###

from itertools import *
from collections import *
from bisect import *
N,K=map(int,input().split())
A=list(map(int,input().split()))

ruiA=[0 for i in range(N+1)]
for i in range(0,N):
    ruiA[i+1]=ruiA[i]+A[i]


nlst=[]

for i in range(len(ruiA)-1):
    for m in range(i+1,len(ruiA)):
        nlst.append(ruiA[m]-ruiA[i])
nlst.sort(reverse=True)

lenbin=60
for i in range(len(nlst)):
    lst=[]
    for m in range(lenbin):
        lst.append((nlst[i]>>m)&1)
    nlst[i]=list(reversed(lst))
lenbinst=0

use=set([i for i in range(len(nlst))])
while lenbinst<lenbin:
    idx=-1
    count=0
    dellst=set()
    for m in use:
        if nlst[m][lenbinst]==1:
            count+=1
    if count>=K:
        if len(nlst)!=count:
            for m in use:
                if nlst[m][lenbinst]!=1:
                    dellst.add(m)
    use=use-dellst
    lenbinst+=1
valuelst=[0 for i in range(lenbin)]
nlst=[nlst[i] for i in use]

for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1

for i in range(lenbin):
    if valuelst[i]>=K:
        newlst=[i for i in nlst if i[idx]==1]
        if len(newlst)>=K:
            nlst=newlst

valuelst=[0 for i in range(lenbin)]
for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1
value=0
for i in range(lenbin):
    if valuelst[i]>=K:
        value+=2**i
print(value)
n,m=map(int,input().split())
a_b=[list(map(int,input().split()))for i in range(n)]
#print(a_b)
#print(index(4))
honsuu=0
money=0
index=0
a=[]
for i in range(n):
    a.append(a_b[i][0])
c=sorted(a)
if len(c)>=2:
	while honsuu<=m:
		money+=a_b[a.index(c[index])][0]*a_b[a.index(c[index])][1]
		honsuu+=a_b[a.index(c[index])][1]
		index+=1
	index-=1
	honsuu-=a_b[a.index(c[index])][1]
	money-=a_b[a.index(c[index])][0]*a_b[a.index(c[index])][1]
	M=m-honsuu
	money+=a_b[a.index(c[index])][0]*M
#print(a_b[a.index(c[0])][1])
#print(index)
	print(money)
else:
	print(a_b[0][0]*a_b[0][1])

### FIXED CODE ###

n,m=map(int,input().split())
x=[list(map(int,input().split())) for i in range(n)]
x.sort(key=lambda x: x[0])
#print(x)
num=0
money=0
for i in range(n):
    num+=x[i][1]
    money+=x[i][1]*x[i][0]
    if num>m:
        money=money-(num-m)*x[i][0]
        break
print(money)
N, M = [int(_) for _ in input().split()]
P = [0] + [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = min(find(x), find(y))
    UF[find(y)] = UF[x]


def same(x, y):
    return find(x) == find(y)


for x, y in XY:
    unite(x, y)

ans = 0
for i in range(1, N + 1):
    if same(i, P[i]):
        ans += 1
print(ans)


### FIXED CODE ###

N, M = [int(_) for _ in input().split()]
P = [0] + [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y in XY:
    unite(x, y)

ans = 0
for i in range(1, N + 1):
    if same(i, P[i]):
        ans += 1
print(ans)
a = input()
if a[0]==a[3]:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

a = input()
if a[0]==a[2]:
  print("Yes")
else:
  print("No")
def get_cost(arr, n, dp):
  if dp[n] != 0:
    return dp[n]
  if n == 1:
    dp[1] = abs(arr[1] - arr[0])
    return dp[1]
  elif n == 0:
    dp[0] = 0
    return dp[0]
  else:
    dp[n] = min(
      abs(arr[n] - arr[n-1]) + get_cost(arr, n-1, dp),
      abs(arr[n] - arr[n-2]) + get_cost(arr, n-2, dp)
    )
    return dp[n]


N = int(input())
arr = [int(num) for num in input().split()]
dp_arr = [0]*N
print(get_cost(arr, N-1, dp_arr))


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)

def get_cost(arr, n, dp):
  if dp[n] != float('inf'):
    return dp[n]
  if n == 1:
    dp[1] = abs(arr[1] - arr[0])
    return dp[1]
  elif n == 0:
    dp[0] = 0
    return dp[0]
  else:
    dp[n] = min(
      abs(arr[n] - arr[n-1]) + get_cost(arr, n-1, dp),
      abs(arr[n] - arr[n-2]) + get_cost(arr, n-2, dp)
    )
    return dp[n]


N = int(input())
arr = [int(num) for num in input().split()]
dp_arr = [float('inf')]*N
print(get_cost(arr, N-1, dp_arr))
while(1):
    a,b=input().strip().split()
    if a<0 or b<0:
        break
    a=int(a)
    b=int(b)
    sum = a+b
    sum = str(sum)
    print(len(sum))

### FIXED CODE ###

import sys

for line in sys.stdin:
    sum = 0
    for x in line.split():
        sum += int(x)
    print(len(str(sum)))
using namespace std;
 
main(){
   int a, b;
   int area, length;
 
    cin >> a >> b;
 
   area = a * b;
   length =2*( a + b);
 
    cout << area << " " << length << endl;
    
 
 
}

### FIXED CODE ###

a, b = map(int, input().split())
print(a*b, a*2 + b*2)
import numpy as np
N=int(input())
A=[int(i) for i in input().split()]
B=np.zeros(N)
for a in range(1,N+1)[::-1]:
    if N % a ==0:
        idx=np.arange(a,N+a,a)-1
    else:
        idx=np.arange(a,N,a)-1
    B[a-1] = (A[a-1] - B[idx].sum()) % 2
B=B 
ans=np.where(B!=0)[0]+1
print(len(ans))
if len(ans)!=0:
    print(*ans)

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[0 for _ in range(N)]
def f(a,N):
    l=[]
    m=2*a
    while m<=N:
        l.append(m)
        m+=a
    return l

for a in range(1,N+1)[::-1]:
    idx=f(a,N)
    b_sum=0
    for i in idx:
        b_sum += B[i-1]
    B[a-1] = (A[a-1] - b_sum) % 2
ans=[i+1 for i in range(N) if B[i] != 0]
print(len(ans))
if len(ans)!=0:
    print(*ans)
n, k = map(int, input().split())
l = [False] * n
c = [0, 0]
for i in range(k):
  p, r = map(input().split())
  if l[int(p) - 1] == False:
    if r == "WA":
      c[0] += 1
    elif r == "AC":
      l[int(p) - 1] = True
      c[1] += 1
print(c[1], c[0])

### FIXED CODE ###

n, m = map(int, input().split())
l = [False] * n
c = [0] * n
ans = [0, 0]
for i in range(m):
  p, r = map(str, input().split())
  if l[int(p) - 1] == False:
    if r == "WA":
      c[int(p) - 1] += 1
    elif r == "AC":
      l[int(p) - 1] = True
      ans[0] += c[int(p) - 1]
      ans[1] += 1
print(ans[1], ans[0])
a = int(input())
b = int(input())
X = b - a 
s = (X*(X + 1))/2 - b
print(s)

### FIXED CODE ###

N = int(input())
if N > 999:
    print('ABD')
elif N <= 999:
    print('ABC')
from collections import deque

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

r = deque(['1'])

fhinish_roop = 0
index = 0
while not fhinish_roop:
    if str(a[index]) not in r:
        r.append(str(a[index]))
        index = a[index] - 1
    else:
        fhinish_roop = 1
        r_2 = "".join(r)
# print(r, index)
roop_l = r_2.find(str(a[index]))
# print(roop_l)
roop_len = len(r) - roop_l
roop_start_index = roop_l
# print(roop_len)

if k < roop_start_index:
    print(a[k - 1])

else:
    ans = (k - roop_start_index) % roop_len
    # print('ans={}'.format(ans))
    print(r[roop_start_index + ans])


### FIXED CODE ###

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

for i in range(n):
    a[i] -= 1

memo = [0] * n

index = 0
memo_index = 0
cnt_k = 1
while 1:
    tmp_move_to = a[index]
    if not memo[tmp_move_to]:
        memo[tmp_move_to] = 1
        index = tmp_move_to
        if cnt_k == k:
            print(tmp_move_to + 1)
            exit()
        cnt_k += 1
    else:
        break
k -= cnt_k

kaburi = tmp_move_to
circle = [kaburi]

index = kaburi
while 1:
    if kaburi == a[index]:
        break
    else:
        circle.append(a[index])
        index = a[index]
# print(circle)
print(circle[k % len(circle)] + 1)
N = input()
a=map(int,raw_input().split())
print(a)
for i in range(1,N):
    v = a[i]
    j = i-1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j-=1
    a[j+1]=v
    print(a)
return

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
for i in range(N):
    v = a[i]
    j = i-1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j-=1
    a[j+1]=v
    print(*a)
x = list(map(int,input().split()))
if x[0] < x[1] :
  print("safe")
  else:
    print("unsafe")


### FIXED CODE ###

x = list(map(int,input().split()))
if x[0] > x[1]:
  print("safe")
else:
  print("unsafe")
"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

# import itertools
# import math

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9

N, M = map(int, readline().split())
AC = 0
WA = 0
li = []
for _ in range(M):
    p, s = readline().decode('utf8').strip().split()
    if p not in li:
        if s != 'AC':
            WA += 1
        else:
            AC += 1
            li.append(p)

print(AC, WA)


### FIXED CODE ###

"""
author : halo2halo
date : 4, Feb, 2020
"""

import sys

# import itertools
# import math

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
INF = 10 ** 9

N, M = map(int, readline().split())
PS = [line.split() for line in readlines()]
AC = [False] * (N + 1)
WA = [0] * (N + 1)

penal = 0
for p, s in PS:
    p = int(p)
    if AC[p]:
        continue
    if s == b'WA':
        WA[p] += 1
    else:
        AC[p] = True
        penal += WA[p]

ac = sum(AC)
print(ac, penal)
import sys
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
hantei = [[0 for _ in range(h)] for _ in range(w)]
for i in range(w-1):
    for j in range(h-1):
        if s[i][j] == "#":
            if s[i+1][j] == "#":
                hantei[i+1][j] = 1
                hantei[i][j] = 1
            if s[i][j+1] == "#":
                hantei[i][j+1] = 1
                hantei[i][j] = 1
for j in range(w-1):
    if s[h-1][j] == "#":
        if s[h-1][j+1] == "#":
            hantei[h-1][j] = 1
            hantei[h-1][j+1] = 1
for i in range(h-1):
    if s[i][w-1] == "#":
        if s[i+1][w-1] == "#":
            hantei[i][w-1] = 1
            hantei[i+1][w-1] = 1


for i in range(w):
    for j in range(h):
        if s[i][j] == "#":
            if hantei[i][j] == 0:
                print("No")
                sys.exit()

print("Yes")

### FIXED CODE ###

import sys
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
hantei = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            if i < h-1:
                if s[i+1][j] == "#":
                    hantei[i][j] = 1
                    hantei[i+1][j] = 1
            if j < w-1:
                if s[i][j+1] == "#":
                    hantei[i][j] = 1
                    hantei[i][j+1] = 1

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            if hantei[i][j] == 0:
                print("No")
                sys.exit()

print("Yes")
N=int(input())
v=list(map(int,input().split()))
while len(v)>1:
  v=v.sort()
  v1=v.pop(0)
  v2=v.pop(0)
  v.append((v1+v2)/2)
print(v[0])

### FIXED CODE ###

N=int(input())
v=list(map(int,input().split()))
while len(v)>1:
  v=sorted(v)
  v_1=v.pop(0)
  v_2=v.pop(0)
  v.append((v_1+v_2)/2)
print(v[0])
def getint(): return int(input())
def getints(): return list(map(int, input().split()))

n,k = getints()
vs = getints()

res = 0
for take in range(0, k + 1):
    sute = k - take
    for from_left in range(0, take+1):
        from_right = k - from_left
        value = []
        for i in range(0, from_left):
            value.append(vs[i])
        for i in range(-1, -from_right, -1):
            value.append(vs[i])
        value = list(sorted(value, reverse=True))
        for i in range(sute):
            if value and value[-1] < 0:
                value.pop()
        tmp = 0 if not value else sum(value)
        res = max(res, tmp)
print(res)


### FIXED CODE ###



def getint(): return int(input())
def getints(): return list(map(int, input().split()))

n,k = getints()
vs = getints()

res = 0
for take_operation in range(0, k + 1):
    sute_operation = k - take_operation
    if take_operation > n:
        continue
    for take_from_left in range(0, take_operation+1):
        take_from_right = take_operation - take_from_left
        item_values = []
        for i in range(0, take_from_left):
            item_values.append(vs[i])
        for i in range(0, take_from_right):
            item_values.append(vs[n - 1 - i])
        item_values = list(sorted(item_values, reverse=True))
        for i in range(sute_operation):
            if item_values and item_values[-1] < 0:
                item_values.pop()
        tmp = 0 if not item_values else sum(item_values)
        res = max(res, tmp)
print(res)
n = int(input())
sum = 0
a_list = list(map(int, input().split()))
# print(a_list)
num = [0] * 10 ** 5
for i in range(n):
    num[a_list[i]] += 1
    sum += a_list[i]

q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    sum += (c - b) * num[b]
    num[c] += num[b]
    num[b] = 0
    print(sum)

    







### FIXED CODE ###

n = int(input())
sum = 0
a_list = list(map(int, input().split()))
num = [0] * (10 ** 5 + 1)
for i in range(n):
    num[a_list[i]] += 1
    sum += a_list[i]

q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    sum += (c - b) * num[b]
    num[c] += num[b]
    num[b] = 0
    print(sum)
n=200000
def pf(x,y,p):
  if y==0: return 1
  if y%2==0:
    d=pf(x,y//2,p)
    return d*d%p
  if y%2==1:
    return (x*pf(x,y-1,p))%p
facl=[1]
for i in range(1,n+2):
  facl.append(facl[i-1]*i%mod)
invl=[1]*(n+2)
for i in range(1,n+2):
  invl[i]=pf(facl[i],mod-2,mod)
def comb(x,k):
  if x<0 or k<0 or x<k: return 0
  if x==0 or k==0: return 1
  return (facl[x]*invl[k]*invl[x-k])%mod
h,w,a,b=map(int,input().split())
mod=10**9+7
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+b-1,b+i)*comb(w-b+a-1,a+i)
print(t%mod)

### FIXED CODE ###

n=200000
mod=10**9+7
def pf(x,y,p):
  if y==0: return 1
  if y%2==0:
    d=pf(x,y//2,p)
    return d*d%p
  if y%2==1:
    return (x*pf(x,y-1,p))%p
facl=[1]
for i in range(1,n+2):
  facl.append(facl[i-1]*i%mod)
invl=[1]*(n+2)
for i in range(1,n+2):
  invl[i]=pf(facl[i],mod-2,mod)
def comb(x,k):
  if x<0 or k<0 or x<k: return 0
  if x==0 or k==0: return 1
  return (facl[x]*invl[k]*invl[x-k])%mod
h,w,a,b=map(int,input().split())
if h-a<w-b:
  h,w=w,h
  a,b=b,a
t=0
for i in range(w-b):
  t+=comb(h-a+b-1,b+i)*comb(w-b+a-1,a+i)
print(t%mod)
N, K, M = list(map(int, input().split()))
A = list(map(int, input().split()))

a_sum = sum(A)
x = N * M - a_sum

if K < x:
    x = -1
elif x < 0:
    x = 0
print(x)


### FIXED CODE ###

c = input()

txt = 'abcdefghijklmnopqrstuvwxyz'
for i in range(26):
    if txt[i] == c:
        print(txt[i + 1])
import math

r = float(input())

print(f'{math.pi * r ** 2} {2 * math,pi * r}')


### FIXED CODE ###

import math

r = float(input())

print(f'{math.pi * r ** 2} {2 * math.pi * r}')
# ABC156D

import numpy as np
def f(n, x):
    mean =  np.mean(x)
    s1 = sum((x-np.floor(mean))**2)
    s2 = sum((x-np.ceil(mean))**2)
    print(int(min(s1, s2)))

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


### FIXED CODE ###

from functools import reduce
def comb(n, r, mod=10 ** 9 + 7):
    numerator = reduce(lambda x, y: x * y % mod, [n - r + k + 1 for k in range(r)])
    denominator = reduce(lambda x, y: x * y % mod, [k + 1 for k in range(r)])
    return numerator * pow(denominator, mod - 2, mod) % mod

n, a, b = map(int, input().split())
mod = 1000000007
print((pow(2, n, mod) - 1 - comb(n, a, mod) - comb(n, b, mod)) % mod)
def fill(s,x,y):
	if 0 <= x <= W-1 and 0 <= y <= H-1 and A[y][x] == s:
		A[y][x] = 0
		fill(s,x+1,y); fill(s,x,y+1); fill(s,x-1,y); fill(s,x,y-1)
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	ans = 0
	for b in range(H):
		for a in range(W):
			if A[b][a] != 0:
				fill(A[b][a],a,b)
				ans += 1
	print ans

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)
def solve(h,w,count,c):
    if 0 <= h < H and 0 <= w < W and A[h][w] == c:
        A[h][w] = count
        for dh,dw in zip([1,0,-1,0],[0,1,0,-1]):
            solve(h+dh,w+dw,count,c)
while 1:
    H,W = map(int,raw_input().split())
    if H == W == 0: break
    A = [list(raw_input()) for _ in range(H)]
    count = 0
    for h in range(H):
        for w in range(W):
            if type(A[h][w]) is not int:
                solve(h,w,count,A[h][w])
                count += 1
    print count
K, X = map(int, input().split())
 for i in range(X - K + 1, X + K):
      if i < X + K - 1:
         print(i, end=' ')
      else:
         print(i)


### FIXED CODE ###

K, X = map(int, input().split())
print(' '.join(map(str, range(X - K + 1, X + K))))
n,x = int(input())
m = []
for i in range(n):
  m = m.append(int(input())) 
print(n + x//min(m))

### FIXED CODE ###

n,x = map(int,input().split())
m = [int(input()) for i in range(n)]
print(n + (x-sum(m))//min(m))
l,r,d=map(int,input().split())
if l > r:
  print(0)
  break
else:
  print((r-l)//d)


### FIXED CODE ###

l,r,d=map(int,input().split())
print(r//d-(l-1)//d)
N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

mod = 10**9+7

m = 10**5 +1 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

E = [[] for _ in [0]*N]
Ef = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)
done = [False]*N
done[0] = True
q = [0]
while q:
    j = q.pop()
    for k in E[j]:
        if done[k]: continue
        done[k] = True
        q.append(k)
        Ef[j].append(k)
        Eb[k].append(j)
Vf = [None]*N
Mf = [None]*N
def getf(i):
    if Mf[i]!=None:
        return Mf[i]
    Mc = [getf(j) for j in Ef[i]]
    Vc = [Vf[j] for j in Ef[i]]
    Vf[i] = 1 + sum(Vc)
    Mf[i] = fac[Vf[i]-1]
    for mc,vc in zip(Mc,Vc):
        Mf[i] *= (mc*finv[vc])%mod
        Mf[i] %= mod
    return Mf[i]

def getp(i):
    if i==0: return 0
    p = Eb[i][0]
    vp = Vf[p]
    vi = Vf[i]
    ret = ans[p]
    ret *= (((fac[vi]*fac[N-1-vi])%mod)*finv[N-1])%mod
    ret %= mod
    ret *= pow(Mf[i],mod-2,mod)
    ret %= mod
    return ret

ans = [0]*N
ans[0] = getf(0)
q = Ef[0].copy()

while q:
    i = q.pop()
    V = [N - Vf[i]]
    M = [getp(i)]
    for j in Ef[i]:
        q.append(j)
        V.append(Vf[j])
        M.append(Mf[j])
    tmp = fac[N-1]
    for mc,vc in zip(M,V):
        tmp *= (mc*finv[vc])%mod
        tmp %= mod
    ans[i] = tmp

for out in ans:
    print(out)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

mod = 10**9+7

m = 10**5*2 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

E = [[] for _ in [0]*N]
Ef = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)
done = [False]*N
done[0] = True
q = [0]
while q:
    j = q.pop()
    for k in E[j]:
        if done[k]: continue
        done[k] = True
        q.append(k)
        Ef[j].append(k)
        Eb[k].append(j)
Vf = [None]*N
Mf = [None]*N
def getf(i):
    if Mf[i]!=None:
        return Mf[i]
    Mc = [getf(j) for j in Ef[i]]
    Vc = [Vf[j] for j in Ef[i]]
    Vf[i] = 1 + sum(Vc)
    Mf[i] = fac[Vf[i]-1]
    for mc,vc in zip(Mc,Vc):
        Mf[i] *= (mc*finv[vc])%mod
        Mf[i] %= mod
    return Mf[i]

def getp(i):
    if i==0: return 0
    p = Eb[i][0]
    vp = Vf[p]
    vi = Vf[i]
    ret = ans[p]
    ret *= (((fac[vi]*fac[N-1-vi])%mod)*finv[N-1])%mod
    ret %= mod
    ret *= pow(Mf[i],mod-2,mod)
    ret %= mod
    return ret

ans = [0]*N
ans[0] = getf(0)
q = Ef[0][:]

while q:
    i = q.pop()
    V = [N - Vf[i]]
    M = [getp(i)]
    for j in Ef[i]:
        q.append(j)
        V.append(Vf[j])
        M.append(Mf[j])
    tmp = fac[N-1]
    for mc,vc in zip(M,V):
        tmp *= (mc*finv[vc])%mod
        tmp %= mod
    ans[i] = tmp

for out in ans:
    print(out)
S = list(input())
ok = ["A", "C", "G", "T"]

len_list = []
tmp = 0

for l in S:
    if l in ok:
        tmp += 1
    else:
        len_list.append(tmp)
        tmp = 0

print(max(len_list))

### FIXED CODE ###

S = list(input())
ok = ["A", "C", "G", "T"]

len_list = []
tmp = 0

for l in S:
    if l in ok:
        tmp += 1
    else:
        len_list.append(tmp)
        tmp = 0
    
len_list.append(tmp)
        
print(max(len_list))
a, b, c = map(int, input().split())
if a**2 + b**2 == c**2:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

import sys
input()
for e in sys.stdin:
    a, b, c = sorted(map(int, e.split()))
    if a**2 + b**2 == c**2:
        print('YES')
    else:
        print('NO')
# coding: utf-8

num, blue_num, red_num = map(int, input().split())
all_ball = blue_num + red_num
if num == 0 or blue_num == 0:
    print(0)
elif red_num == 0:
    print(num)
else:
    count = int(num / all_ball)
    rest = int(num - (count * all_ball))
    if rest <= blue_num:
        blue = rest
    print((count) * blue_num + blue)



### FIXED CODE ###

# coding: utf-8
import math

count = 0
num, blue_num, red_num = map(int, input().split())
all_ball = blue_num + red_num
count = num // all_ball
rest = num % all_ball
print(count * blue_num + min(rest, blue_num))
l = input()
V = (l/3)**3
print(V)

### FIXED CODE ###

l = int(input())
V = (l/3)**3
print(V)
def main():
    # importも関数の中で実装する
    # ローカル変数化する
    # xxx
    N, N = map(int, input().split())
    SC = [list(map(int, input().split())) for _ in [0]*N ]
    SC.sort()

    num = (10 ** N) - 1
    keta = 1

    if SC[0][0] != 0:
        print('-1')
        exit()

    for S,C in SC:
        if S == 1 and C == 0:
            print('-1')
            exit()

        if S == keta:
            tmp = C * (10 ** (N - S))
            if tmp < num:
                num = tmp
        elif S > keta:
            keta = S
            tmp = C * (10 ** (N - S))
            num += tmp

    print(num)


main()

### FIXED CODE ###

n,m,*z=map(int,open(0).read().split())
for i in range(10**n):
  S=str(i)
  if len(S)==n:
    if all(S[s-1]==str(c)for s,c in zip(z[0::2],z[1::2])):
      print(S)
      quit()
print(-1)
A, P = map(int, input().split())

print(A * 3 // P)

### FIXED CODE ###

A, P = map(int, input().split())

print((A * 3 + P) // 2)