Problem:
 Score : 600 points    Problem Statement  We have a tree with N vertices numbered 1 to N . The i -th edge in this tree connects Vertex a_i and b_i .
For each k=1, ..., N , solve the problem below:   Consider writing a number on each vertex in the tree in the following manner:  First, write 1 on Vertex k .  Then, for each of the numbers 2, ..., N in this order, write the number on the vertex chosen as follows:  Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.      Find the number of ways in which we can write the numbers on the vertices, modulo (10^9+7) .       Constraints   2 \leq N \leq 2 \times 10^5  1 \leq a_i,b_i \leq N  The given graph is a tree.         Input  Input is given from Standard Input in the following format:  N  a_1  b_1  :  a_{N-1}  b_{N-1}       Output  For each k=1, 2, ..., N in this order, print a line containing the answer to the problem.        Sample Input 1 3
1 2
1 3      Sample Output 1 2
1
1  The graph in this input is as follows:   For k=1 , there are two ways in which we can write the numbers on the vertices, as follows:   Writing 1, 2, 3 on Vertex 1, 2, 3 , respectively  Writing 1, 3, 2 on Vertex 1, 2, 3 , respectively        Sample Input 2 2
1 2      Sample Output 2 1
1  The graph in this input is as follows:        Sample Input 3 5
1 2
2 3
3 4
3 5      Sample Output 3 2
8
12
3
3  The graph in this input is as follows:        Sample Input 4 8
1 2
2 3
3 4
3 5
3 6
6 7
6 8      Sample Output 4 40
280
840
120
120
504
72
72  The graph in this input is as follows:

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N = ir()
graph = [[] for _ in range(N+1)]  
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

MOD = 10 ** 9 + 7

fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD
fact_inv = [1] * (N + 10)
fact_inv[-1] = pow(fact[-1], MOD - 2, MOD)
for n in range(N + 9, 0, -1):
    fact_inv[n - 1] = fact_inv[n] * n % MOD

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    cur = stack.pop()
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        stack.append(next)

size_down = [0] * (N+1)  
dp_down = [1] * (N+1)  
for v in order[::-1]:
    dp_down[v] *= fact[size_down[v]]
    dp_down[v] %= MOD
    p = parent[v]
    s = size_down[v] + 1
    size_down[p] += s
    dp_down[p] *= fact_inv[s] * dp_down[v]
    dp_down[p] %= MOD

size_up = [N-x-1 for x in size_down]  
dp_up = [1] * (N+1)  
for v in order[1:]:
    p = parent[v]
    x = dp_down[p]
    x *= dp_up[p]
    x *= fact_inv[size_down[p]]
    x *= fact[size_down[v] + 1]
    x *= pow(dp_down[v], MOD-2, MOD)
    x %= MOD
    x *= fact[size_up[v]-1]
    x *= fact_inv[size_up[p]]
    dp_up[v] = x % MOD

size_up[1] = 0; dp_up[1] = 1
for xd, xu, sd, su in zip(dp_down[1:], dp_up[1:], size_down[1:], size_up[1:]):
    answer = xd * xu * fact[sd+su] * fact_inv[sd] * fact_inv[su] % MOD
    print(answer % MOD)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()


P = 10**9 + 7
N = 200001 
inv = [0] + [1] 
finv = [1] + [1] 
fac = [1] + [1] 
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b): return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P




class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b


zero = T(1, 0)

def step(x):
    return T(x.num, x.child+1)

def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(N)]
down_data = [zero] * N
dat = [zero] * N
rev_data = [zero] * N

class p:
    num = -1
    parent = -1

    def __init__(self, x, y):
        self.num = x
        self.parent = y
node_list = []
def makeNodeList(root):
    
    stack = []
    stack.append(p(root, -1))
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now.num]:
            if to == now.parent: continue
            stack.append(p(to, now.num))
    node_list.reverse()

def dfs(root):
    for now in node_list:
        for to in G[now.num]:
            if to == now.parent: continue
            down_data[now.num] = merge(down_data[now.num], step(down_data[to]))

def dfs_rev(root):
    for now in node_list:
        
        rev = rev_data[now.num]
        left = []
        right = []
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            if len(left)==0: left.append(step(down_data[to]))
            else: left.append(merge(left[cnt-1], step(down_data[to])))
            cnt += 1
        cnt = 0
        for to in reversed(G[now.num]):
            if to==now.parent: continue
            if len(right)==0: right.append(step(down_data[to]))
            else: right.append(merge(right[cnt-1], step(down_data[to])))
            cnt += 1
        dat[now.num] = merge(rev, down_data[now.num])
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            x = zero if cnt==0 else left[cnt-1]
            y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
            rev_data[to] = step(merge(rev, merge(x, y)))
            cnt += 1

def calc(data_num):
    root = -1
    for i in range(1, data_num+1):
        if len(G[i]) == 1:
            root = i
            break
    makeNodeList(root)
    dfs(root)
    node_list.reverse()
    dfs_rev(root)

def main():
    n = int(input())
    for i in range(n-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    calc(n)

    for i in range(1, n+1): print(dat[i].num)

if __name__ == "__main__": main()

Solution (Python):
import sys
input = sys.stdin.readline

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

MOD = 10 ** 9 + 7

F = Factorial(2 * 10 ** 5 + 10, MOD)

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


root = 1

DAG = []
parent = [-1] * (N + 1)
parent[root] = 0
stack = [root]
while stack:
    now_ = stack.pop()
    DAG.append(now_)
    for next_ in G[now_]:
        if parent[next_] == -1:
            stack.append(next_)
            parent[next_] = now_



size1 = [1] * (N + 1)
dp1 = [1] * (N + 1)

for i in DAG[::-1]:
    size1[parent[i]] += size1[i]

for i in DAG[::-1]:
    dp1[i] *= F.factorial(size1[i] - 1)
    dp1[i] %= MOD
    dp1[parent[i]] *= (dp1[i] * F.ifactorial(size1[i])) % MOD
    dp1[parent[i]] %= MOD




size2 = [1] * (N + 1)
dp2 = [1] * (N + 1)

for i in DAG[::]:
    for j in G[i]:
        if parent[i] == j:
            continue
        size2[j] = size2[i] + size1[i] - size1[j]  

for i in DAG[1::]:
    x = 1
    x *= dp1[parent[i]]
    x *= F.ifactorial(size1[parent[i]] - 1)
    x *= F.factorial(size1[i])
    x *= pow(dp1[i], MOD - 2, MOD)
    x *= dp2[parent[i]]
    x *= F.ifactorial(size2[parent[i]] - 1)
    x *= F.factorial(size2[i] - 2)
    dp2[i] = x % MOD







fact = F.factorial(N - 1)
for x in range(1, N + 1):
    ans = fact * dp1[x] * F.ifactorial(size1[x] - 1) * dp2[x] * F.ifactorial(size2[x] - 1)
    print (ans % MOD)

Solution (Python):

"""
Created on Fri May  8 12:10:59 2020

@author: ybt07
"""

import sys
sys.setrecursionlimit(3*10**5)  


N = 2*10**5   
MOD = 10**9 + 7




class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    
    '''
    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )
    '''

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * inv[other.x]
            ) if isinstance(other, ModInt) else
            ModInt(self.x * inv[other])
        )


    
    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    
    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return ModInt(fac[n] * facinv[r] * facinv[n-r])

fac = [1, 1] 
facinv = [1, 1] 
inv = [0, 1] 

for i in range(2, N):
    fac.append( ( fac[-1] * i ) % MOD )
    inv.append( ( -inv[MOD % i] * (MOD//i) ) % MOD )
    facinv.append( (facinv[-1] * inv[-1]) % MOD )





def dfs(u, p = -1):

    global DP, CN, E
    
    tmp_ans = 1
    tmp_cn = 0  

    
    for v in E[u]:
        if v != p:  
            DP[v], CN[v] = dfs(v, u)
            tmp_cn += CN[v]
            tmp_ans *= DP[v] * cmb(tmp_cn, CN[v])
    DP[u] = tmp_ans
    CN[u] = tmp_cn + 1
            
    return tmp_ans, tmp_cn + 1



def bfs(u, p=-1):
    
    global DP, E
    
    tmp_ans = DP[u]
    tmp_cn = 1
    
    for v in E[u]:  
        if v == p:
            continue
            
        
        tmp_cn = N - CN[v]  
        
        
                
        
        

        
        
                
        
        DP[v] = DP[u] * CN[v] / (N - CN[v]) 

        bfs(v, u)
    
    return


N = int(input())  
E = [[] for _ in range(N)]  

for _ in range(N - 1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)  
    E[b-1].append(a-1)
    
DP = [ModInt(1)] * N
CN = [0] * N

dfs(0)
bfs(0)

for i in DP:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(200005)
n = int(input())
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class comb():
    
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) 
        ifact = [0]*(n+1) 
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if n == 0:
            return 1
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]
cb = comb(200005)

class datum:
    def __init__(self, size=0, case=None):
        self.size = size
        if case is None:
            self.case = mint(1)
        else:    
            self.case = case

def merge(now, plus):
    ressize = now.size + plus.size
    rescase = now.case*plus.case
    rescase *= cb.ifact[plus.size]
    return datum(ressize,rescase)

def add_root(now):
    rescase = now.case * cb.fact[now.size]
    ressize = now.size + 1
    return datum(ressize,rescase)

def dfs(u,p=-1):
    now = datum()
    for v in to[u]:
        if v == p:
            continue
        dp[u][v] = dfs(v,u)
        now = merge(now,dp[u][v])
    now = add_root(now)
    return now

ans = [mint(0) for _ in range(n)]
def bfs(u,p=-1,pdp=None):
    for v in to[u]:
        if v == p:
            dp[u][v] = pdp
    deg = len(to[u])
    l = [datum() for _ in range(deg+1)]
    r = [datum() for _ in range(deg+1)]
    for i in range(deg):
        l[i+1] = merge(l[i], dp[u][to[u][i]])
    for i in reversed(range(1,deg+1)):
        r[i-1] = merge(r[i], dp[u][to[u][i-1]])

    ans[u] = add_root(l[-1]).case

    for i in range(deg):
        v = to[u][i]
        if v == p:
            continue
        argdp = datum()
        argdp.size += l[i].size + r[i+1].size
        argdp.case *= l[i].case * r[i+1].case
        bfs(v,u,add_root(argdp))







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

dfs(0)
bfs(0)

print(*ans)

Solution (Python):
MOD = 10 ** 9 + 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

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

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

Solution (Python):
def hoge():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))

    from collections import defaultdict
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)


    M = 10**9+7 
    N = n 

    g1 = [None] * (N+1) 
    g2 = [None] * (N+1) 
    inverse = [None] * (N+1) 
    g1[0] = g1[1] = g2[0] = g2[1] = 1
    inverse[0], inverse[1] = [0, 1] 

    for i in range( 2, N + 1 ):
        g1[i] = ( g1[i-1] * i ) % M 
        inverse[i] = ( -inverse[M % i] * (M//i) ) % M 
        g2[i] = (g2[i-1] * inverse[i]) % M 


    ans = {}
    prevs = {}
    out = [None] * n
    def sub(i, j, prev):
        prevs[i,j] = prev
        if (i,j) in ans:
            return ans[i,j]
        if len(ns[j])==1 and i in ns[j]:
            ans[i,j] = (1, 1)
            return (1, 1)

        count = 1
        sum_size = 0
        for k in ns[j]:
            if k==i:
                continue
            val, size = sub(j, k, i)
            count = (count * val) % M
            count = (count * g2[size]) % M
            sum_size += size
        count = (count * g1[sum_size]) % M
        ans[i,j] = (count, sum_size+1)
        return (count, sum_size+1)

    def sub2(i, j, q):
        for k in ns[j]:
            if k==i:
                continue
            if (k, j) in ans:
                continue
            tmp_count, tmp_size = ans[j, k]
            total_count, total_size = ans[prevs[j, k], j]
            prev_count, prev_size = ans[j, i]
            new_size = total_size - tmp_size + prev_size
            new_count = (total_count * g2[total_size-1] * g1[new_size-1]) % M
            new_count = (new_count * prev_count * pow(tmp_count, M-2, M)) % M
            new_count = (new_count * g2[prev_size] * g1[tmp_size]) % M
            ans[k, j] = (new_count, new_size)
            val = tmp_count
            val = (val * new_count * g1[new_size+tmp_size-1] * g2[tmp_size-1] * g2[new_size]) % M
            out[k] = val
            q.appendleft((j, k))

    
    
    
    
    
    

    
    sub(-1, 0, None)

    ans[0, -1] = (1,0)

    
    from queue import deque
    q = deque()
    q.appendleft((-1, 0))
    while q:
        u, v = q.pop()
        sub2(u, v, q)
    
    u = 0
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] 
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    out[0] = count
    return out
out = hoge()
print("\n".join(map(str, out)))

Solution (Python):
def hoge():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


    from collections import defaultdict
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)


    M = 10**9+7 
    N = n 

    g1 = [None] * (N+1) 
    g2 = [None] * (N+1) 
    inverse = [None] * (N+1) 
    g1[0] = g1[1] = g2[0] = g2[1] = 1
    inverse[0], inverse[1] = [0, 1] 

    for i in range( 2, N + 1 ):
        g1[i] = ( g1[i-1] * i ) % M 
        inverse[i] = ( -inverse[M % i] * (M//i) ) % M 
        g2[i] = (g2[i-1] * inverse[i]) % M 


    ans = {}
    prevs = {}
    out = [None] * n
    def sub(i, j, prev):
        prevs[i,j] = prev
        if (i,j) in ans:
            return ans[i,j]
        if len(ns[j])==1 and i in ns[j]:
            ans[i,j] = (1, 1)
            return (1, 1)

        count = 1
        sum_size = 0
        for k in ns[j]:
            if k==i:
                continue
            val, size = sub(j, k, i)
            count = (count * val) % M
            count = (count * g2[size]) % M
            sum_size += size
        count = (count * g1[sum_size]) % M
        ans[i,j] = (count, sum_size+1)
        return (count, sum_size+1)

    def sub2(i, j):
        for k in ns[j]:
            if k==i:
                continue
            if (k, j) in ans:
                continue
            tmp_count, tmp_size = ans[j, k]
            total_count, total_size = ans[prevs[j, k], j]
            prev_count, prev_size = ans[j, i]
            new_size = total_size - tmp_size + prev_size
            new_count = (total_count * g2[total_size-1] * g1[new_size-1]) % M
            new_count = (new_count * prev_count * pow(tmp_count, M-2, M)) % M
            new_count = (new_count * g2[prev_size] * g1[tmp_size]) % M
            ans[k, j] = (new_count, new_size)
            val = tmp_count
            val = (val * new_count * g1[new_size+tmp_size-1] * g2[tmp_size-1] * g2[new_size]) % M
            out[k] = val
            sub2(j, k)
    
    
    
    
    
    

    
    sub(-1, 0, None)

    ans[0, -1] = (1,0)

    
    sub2(-1, 0)
    
    u = 0
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] 
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    out[0] = count
    print("\n".join(map(str, out)))
hoge()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    class Rerooting():
        def __init__(self):
            
            
            
            
            
            def merge(a, b): return a * b % mod
            def adj_bu(a, i): return a * inv[size[i]] % mod
            def adj_td(a, i, p): return a * inv[n-size[i]] % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            
            
            
            
            
            T = g
            P = [-1]*n
            q = [0]
            ini = 1
            order = []
            while q:
                i = q.pop()
                order.append(i)
                for a in T[i]:
                    if a != P[i]:
                        P[a] = i
                        T[a].remove(i)
                        q.append(a)

            T = [list(i) for i in T]

            
            
            size = [1]*n
            for i in order[1:][::-1]:
                size[P[i]] += size[i]

            
            
            
            ME = [ini]*n
            DP = [0]*n
            for i in order[1:][::-1]:
                DP[i] = adj_bu(ME[i], i)
                p = P[i]
                ME[p] = merge(ME[p], DP[i])
            DP[order[0]] = adj_fin(ME[order[0]], order[0])
            TD = [ini]*n

            
            for i in order:
                
                ac = TD[i]
                for j in T[i]:
                    TD[j] = ac
                    ac = merge(ac, DP[j])
                
                
                
                
                
                
                
                
                
                
                ac = ini
                for j in T[i][::-1]:
                    TD[j] = adj_td(merge(TD[j], ac), j, i)
                    ac = merge(ac, DP[j])
                    DP[j] = adj_fin(merge(ME[j], TD[j]), j)
            for i in DP:
                print(i)
    Rerooting()


main()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class Tree:
    def __init__(self, crdinal, adjgrph, root):
        self.n = crdinal
        self.g = adjgrph
        self.root = root
        self.parent = [-1]*self.n
        self.depth = [-1]*self.n
        self.subsize = [1]*self.n
        self.dp = [1]*self.n  

        s = [self.root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == self.root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.g[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.calc(v)

        for i in range(n):
            self.dp[i] *= fact[self.subsize[i]-1]
            self.dp[i] %= mod

    def calc(self, v):
        
        self.dp[self.parent[v]] *= fact[self.subsize[v]-1] * self.dp[v] * ifact[self.subsize[v]]
        self.dp[self.parent[v]] %= mod
        return None

    def wanted(self):
        
        
        return self.parent

    def rerooting(self) -> list:
        
        ans = [0]*n
        ans[self.root] = self.dp[self.root]

        FromParent = [0]*n

        s = [self.root]
        while s:
            v = s.pop()
            cum = 1

            for w in self.g[v]:
                if w != self.parent[v]:
                    cum *= self.dp[w]*ifact[self.subsize[w]]
                    cum %= mod
                    s.append(w)
                else:
                    cum *= FromParent[v]*ifact[n-self.subsize[v]]
                    cum %= mod

            
            
            for i, w in enumerate(self.g[v]):
                if w != self.parent[v]:
                    FromParent[w] = fact[n-self.subsize[w]-1] * cum * inv(self.dp[w] * ifact[self.subsize[w]] , mod)
                    ans[w] = fact[n-1] * (FromParent[w] * ifact[n-self.subsize[w]]) * (self.dp[w] * ifact[self.subsize[w]-1])
                    ans[w] %= mod
        return ans


mod = 10**9+7


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    
    return (mod+x % mod) % mod


max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod

ifact[max_num-1] = inv(fact[max_num-1], mod)

for i in range(2, max_num):
    ifact[max_num-i] = (ifact[max_num-i+1] * (max_num-i+1)) % mod


n = int(input())
g = [[] for _ in range(n)]

for _ in range(n-1):
    x, y = map(int, input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)

T1 = Tree(n, g, 0)

for x in T1.rerooting():
    print(x)

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    def Reroot():
        
        
        
        
        
        def merge(a, b): return a * b % mod
        def adj_bu(a, i): return a * inv[size[i]] % mod
        def adj_td(a, i, p): return a * inv[n-size[i]] % mod
        def adj_fin(a, i): return a * fact[n-1] % mod

        
        
        
        
        
        T = g
        P = [-1]*n
        q = [0]
        ini = 1
        order = []
        while q:
            i = q.pop()
            order.append(i)
            for a in T[i]:
                if a != P[i]:
                    P[a] = i
                    T[a].remove(i)
                    q.append(a)

        T = [list(i) for i in T]

        
        
        size = [1]*n
        for i in order[1:][::-1]:
            size[P[i]] += size[i]

        
        
        
        ME = [ini]*n
        DP = [0]*n
        for i in order[1:][::-1]:
            DP[i] = adj_bu(ME[i], i)
            p = P[i]
            ME[p] = merge(ME[p], DP[i])
        DP[order[0]] = adj_fin(ME[order[0]], order[0])
        TD = [ini]*n

        
        for i in order:
            
            ac = TD[i]
            for j in T[i]:
                TD[j] = ac
                ac = merge(ac, DP[j])
            
            
            
            
            
            
            
            
            
            
            ac = ini
            for j in T[i][::-1]:
                TD[j] = adj_td(merge(TD[j], ac), j, i)
                ac = merge(ac, DP[j])
                DP[j] = adj_fin(merge(ME[j], TD[j]), j)
        for i in DP:
            print(i)
    Reroot()


main()