Nauuo is a girl who loves drawing circles.

One day she has drawn a circle and wanted to draw a tree on it.

The tree is a connected undirected graph consisting of $n$ nodes and $n-1$ edges. The nodes are numbered from $1$ to $n$.

Nauuo wants to draw a tree on the circle, the nodes of the tree should be in $n$ distinct points on the circle, and the edges should be straight without crossing each other.

"Without crossing each other" means that every two edges have no common point or the only common point is an endpoint of both edges.

Nauuo wants to draw the tree using a permutation of $n$ elements. A permutation of $n$ elements is a sequence of integers $p_1,p_2,\ldots,p_n$ in which every integer from $1$ to $n$ appears exactly once.

After a permutation is chosen Nauuo draws the $i$-th node in the $p_i$-th point on the circle, then draws the edges connecting the nodes.

The tree is given, Nauuo wants to know how many permutations are there so that the tree drawn satisfies the rule (the edges are straight without crossing each other). She only wants to know the answer modulo $998244353$, can you help her?

It is obvious that whether a permutation is valid or not does not depend on which $n$ points on the circle are chosen.


-----Input-----

The first line contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$), denoting there is an edge between $u$ and $v$.

It is guaranteed that the given edges form a tree.


-----Output-----

The output contains a single integer — the number of permutations suitable to draw the given tree on a circle satisfying the rule, modulo $998244353$.


-----Examples-----
Input
4
1 2
1 3
2 4

Output
16
Input
4
1 2
1 3
1 4

Output
24


-----Note-----

Example 1

All valid permutations and their spanning trees are as follows.

[Image]

Here is an example of invalid permutation: the edges $(1,3)$ and $(2,4)$ are crossed.

[Image]

Example 2

Every permutation leads to a valid tree, so the answer is $4! = 24$.

Difficulty: competition

Starter code:

Solutions:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))

def main():
    n = I()
    aa = [LI() for _ in range(n-1)]
    e = collections.defaultdict(set)
    for a,b in aa:
        e[a].add(b)
        e[b].add(a)

    q = [[(1,-1)]]
    qi = 0
    while 1:
        t = q[qi]
        nq = []
        for i,p in t:
            for c in e[i]:
                if c == p:
                    continue
                nq.append((c,i))
        if len(nq) < 1:
            break
        q.append(nq)
        qi += 1

    gm = [1]
    for i in range(1,n+1):
        gm.append(i*gm[-1]%mod)

    m = {}
    def f(i, p):
        t = 1
        r = 1
        for c in e[i]:
            if c == p:
                continue
            # print('c',c)
            r *= m[c]
            r %= mod
            t += 1

        if p == -1:
            r *= gm[t-1]
            r *= n
        else:
            r *= gm[t]
        r %= mod
        m[i] = r
        # print('r',i,p,r)
        # print('g',gm[t],t)
        return r

    for qt in q[::-1]:
        for i,p in qt:
            # print('ip', i,p)
            f(i,p)

    r = f(1,-1)

    return r


print(main())



import sys
input = sys.stdin.readline
MOD = 998244353
fa = [1]
for i in range(1, 2*10**5+10):
    fa.append(fa[-1]*i%MOD)

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = list(map(int, input().split()))
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = [0]
while Q:
    i = Q.pop()
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            Q.append(a)

ans = N
for i in range(len(X)):
    ans = ans * fa[len(X[i])+(1 if i else 0)] % MOD
print(ans)


p=998244353
n=int(input())
facs=[1]
for i in range(1,n):
    facs.append(facs[-1]*i%p)
graph=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    graph[u-1].append(v-1)
    graph[v-1].append(u-1)
prod=facs[len(graph[0])]*n
for i in range(1,n):
    k=len(graph[i])
    prod=prod*facs[k]%p
print(prod)

p=998244353
n=int(input())
facs=[1]
for i in range(1,n):
    facs.append(facs[-1]*i%p)
graph=[0]*n
for i in range(n-1):
    u,v=map(int,input().split())
    graph[u-1]+=1
    graph[v-1]+=1
prod=n
for i in range(n):
    prod=prod*facs[graph[i]]%p
print(prod)

mod=998244353
n=int(input())
deg=[0]*(n+1)
fac=[1]*(n+1)
for i in range(1,n+1):
    fac[i]=(fac[i-1]*i)%mod
for i in range(n-1):
    a,b=list(map(int,input().split()))
    deg[a]+=1
    deg[b]+=1
s=1
for i in range(1,n+1):
    s=(s*(fac[deg[i]]))%mod
s=(s*n)%mod
print(s)
    


import io, os
#input = io.StringIO(os.read(0, os.fstat(0).st_size).decode()).readline


g = [0] * 200005

r = int(input())
n = r

for i in range(1, n):
	u, v = list(map(int, input().split()))
	g[u] += 1
	g[v] += 1
	r *= g[u] * g[v]
	r %= 998244353

print(r)


import math
def factorial(n,j):
    inf=998244353
    j[0]=1
    j[1]=1
    for i in range(2,n+1):
        j[i]=j[i-1]*i
        j[i]%=inf
    return j


l1=[0]*(200009)
y=factorial(200008,l1)
inf=998244353
n=int(input())
l=[0]*(200009)
x=1
for i in range(n-1):
    u,v=input().split()
    u,v=[int(u),int(v)]
    l[u]+=1
    l[v]+=1
for i in range(len(l)):
    if l[i]>0:
        x*=y[l[i]]
        x%=inf
print((n*x)%inf)


import math
def factorial(n,j):
    inf=998244353
    j[0]=1
    j[1]=1
    for i in range(2,n+1):
        j[i]=j[i-1]*i
        j[i]%=inf
    return j


l1=[0]*(200009)
y=factorial(200008,l1)
inf=998244353
n=int(input())
l=[0]*(200009)
x=1
for i in range(n-1):
    u,v=input().split()
    u,v=[int(u),int(v)]
    l[u]+=1
    l[v]+=1
for i in range(len(l)):
    if l[i]>0:
        x*=y[l[i]]
        x%=inf
print((n*x)%inf)



g = [0] * 200005
 
r = int(input())
n = r
 
for i in range(1, n):
	u, v = map(int, input().split())
	g[u] += 1
	g[v] += 1
	r *= g[u] * g[v]
	r %= 998244353


print(r)

import  sys
input=sys.stdin.readline
#sys.setrecursionlimit(1000000)

n=int(input())
fr=[0]*(n+2)
fr[0]=1
d=[0]*(n+2)
mod=int(998244353)

for i in range(1,n+1):
    fr[i]=(fr[i-1]*i)%mod

for i in  range(n-1):
    u,v=map(int,input().split())
    d[u]+=1;d[v]+=1

ans=n

for i in range(1,n+1):
    ans=ans*fr[d[i]]
    ans%=mod

print(ans)