201303: [AtCoder]ARC130 D - Zigzag Tree

Problem Statement

Given is a tree with $N$ vertices. The vertices are numbered $1$ to $N$, and the $i$-th edge connects Vertices $a_i$ and $b_i$.

Find the number of sequences of positive integers $P = (P_1, P_2, \ldots, P_N)$ that satisfy the conditions below, modulo $998244353$.

• $1\leq P_i\leq N$
• $P_i\neq P_j$ if $i\neq j$.
• For $1\leq a, b, c\leq N$, if Vertices $a$ and $b$ are adjacent, and Vertices $b$ and $c$ are also adjacent, $P_a < P_b > P_c$ or $P_a > P_b < P_c$ holds.

Constraints

• $2\leq N\leq 3000$
• $1\leq a_i, b_i\leq N$
• The given graph is a tree.

Input

Input is given from Standard Input in the following format:

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

Output

Print the answers.

Sample Input 1

3
1 2
2 3

Sample Output 1

4

The $4$ sequences satisfying the conditions are:

• $P = (1, 3, 2)$
• $P = (2, 1, 3)$
• $P = (2, 3, 1)$
• $P = (3, 1, 2)$

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

12

Sample Input 3

6
1 2
2 3
3 4
4 5
5 6

Sample Output 3

122

Sample Input 4

9
8 5
9 8
1 9
2 5
6 1
7 6
3 8
4 1

Sample Output 4

19080