题目描述

There is a tree with $N$ nodes numbered from $1$ to $N$. For each $i = 1, \ldots, 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 of colors $(A, B)$ 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.

$$\begin{aligned} &N \\ &u_1 \ v_1 \\ &u_2 \ v_2 \\ &\vdots \\ &u_{N-1} \ v_{N-1} \end{aligned} $$

The first line consists of an integer $N$, which satisfies $1 \leq N \leq 2,000$. Each of the $N - 1$ lines consists of two integers $u_i, v_i$, which satisfies $1 \leq u_i, v_i \leq 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$.

4
1 2
2 3
3 4

16

4
1 2
1 3
1 4

24