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