시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB249866.667%

문제

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$.

예제 입력 1

4
1 2
2 3
3 4

예제 출력 1

16

예제 입력 2

4
1 2
1 3
1 4

예제 출력 2

24