Problem Statement

There is a tree with $N$ vertices numbered $1$ to $N$. The $i$-th edge connects vertices $u_i$ and $v_i$. Additionally, there are $N$ pieces numbered $1$ to $N$. Initially, piece $i$ is placed on vertex $i$. You can perform the following operation any number of times, possibly zero:

• Choose one edge. Let vertices $u$ and $v$ be the endpoints of the edge, and swap the pieces on vertices $u$ and $v$. Then, delete the chosen edge.

Let $a_i$ be the piece on vertex $i$. How many different possible sequences $(a_1, a_2, \dots, a_N)$ exist when you finish performing the operation? Find the count modulo $998244353$.

Constraints

• $2 \leq N \leq 3000$
• $1 \leq u_i \lt v_i \leq N$
• The graph given in the input is a tree.

Input

The input is given from Standard Input in the following format:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Print the number, modulo $998244353$, of possible sequences $(a_1, a_2, \dots, a_N)$.