Orderings

Today Carol has a day off. Even on this beautiful spring day, though, she does not rest. She trains to prepare for fights with the Skrulls. One important skill is finding your way quickly in unfamiliar places, so to sharpen it, Carol invited her mentor Ion-Rogg.

Carol and Ion-Rogg play the following game. First, Ion-Rogg draws a map of a Skrull hideout on paper. The map consists of $n$ rooms, numbered from $1$ to $n$. Some pairs of rooms are connected by two-way passages. The hideout is built so that every room can be reached from every other room by moving through the passages. To keep the game from getting too hard, Ion-Rogg draws exactly $n - 1$ passages. In other words, the hideout map is a tree.

The Skrulls use special robots to carry cargo between rooms. The robots are simple and navigate the hideout poorly. To solve this, the Skrulls chose exactly one direction for each passage, and robots may travel only along that direction.

After drawing the map, Ion-Rogg marks the direction of robot travel on each passage. In other words, he orients the edges of the drawn tree.

Carol must write a list of all room numbers in some order. The list must satisfy the following condition: for every passage, a robot travels from the room that comes earlier in the list to the room that comes later. Formally, Carol must write a permutation $p_1 p_2 \ldots p_n$ such that if a robot can travel along a passage from room $p_i$ to room $p_j$, then $i < j$.

While Carol works on her task, Ion-Rogg wonders how many permutations satisfy this condition. Since the answer can be very large, he asks only for its remainder modulo $998\,244\,353$.

The first line contains one integer $n$, the number of rooms in the hideout drawn by Ion-Rogg ($1 \le n \le 3\,000$).

Each of the next $n - 1$ lines contains two integers $a$ and $b$, the numbers of the rooms connected by a passage. Robots travel along that passage from room $a$ to room $b$.

The hideout is guaranteed to be a tree. That is, every room can be reached from every other room by moving along the passages, in either direction regardless of the robot travel direction.

Print the remainder modulo $998\,244\,353$ of the number of distinct permutations $p_1 p_2 \ldots p_n$ that satisfy the condition: if a robot can travel along a passage from room $p_i$ to room $p_j$, then $i < j$.

In the first test, Carol can write two permutations: $\{1, 2, 3\}$ or $\{1, 3, 2\}$.

In the second test, Carol can write three permutations: $\{2, 3, 1, 4\}$, $\{2, 3, 4, 1\}$, or $\{2, 4, 3, 1\}$.