30369번 - Many-hued Tree 다국어

문제

There is a tree with $N$ nodes numbered from 1ドル$ to $N$. For each $i = 1, \dots, N-1,ドル the $i$-th edge connects node $u_i$ and node $v_i$.

You are going to paint all nodes in distinct colors. Colors are represented by integers between 1ドル$ and $N$.

The assignment of colors on the tree is called good, if it is possible to complete the following operation $N-1$ times repeatedly.

• Select a pair $(A, B)$ of colors which satisfies the following two conditions.
  • $|A - B| = 1$.
  • There exists an edge which connects a node painted in color $A$ and a node painted in color $B$.
• Change the color of all nodes currently painted in color $A$ to color $B$.

Your task is to count the number of good assignments of colors on the tree modulo 998ドル,244円,353円$.

입력

The input consists of a single test case of the following format.

$N$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

The first line consists of an integer $N,ドル which satisfies 1ドル \le N \le 2,000円$. Each of the $N-1$ lines consists of two integers $u_i,ドル $v_i,ドル which satisfies 1ドル \le u_i, v_i \le N$. The given graph is guaranteed to be a tree.

출력

Output in a line the number of assignments of colors on the given tree modulo 998ドル,244円,353円$.

제한

힌트