Description
Little Q has two rooted trees, one called $A$ and one called $B$.
These two rooted trees are peculiar: they each have a specific node called the "root node," denoted as $S_A, S_B$, and another specific node called the "anti-root node," denoted as $T_A, T_B$. We call such trees (trees with a "root node" and an "anti-root node") "double-rooted trees." (Note: The root node and the anti-root node may be the same node.)
Little Q wants to multiply them to form a new double-rooted tree. The operation is as follows (see the formal description and example at the end of the problem):
- First, for every node $a$ in $A$, make a copy of tree $B$, denoted as $B_a$.
- Then, if $x$ is the parent of $y$ in tree $A$, add an edge between the root node of $B_y$ and the anti-root node of $B_x$ (in fact, the latter will become the parent of the former in the new tree).
- The root node of the new tree is the root node of $B_{S_A}$, and the anti-root node is the anti-root node of $B_{T_A}$.
Let this new double-rooted tree be denoted as $A \circ B$. It is easy to see that the number of nodes in $A \circ B$ is the product of the number of nodes in the two trees.
Now, Little Q has a double-rooted tree $A$ with $n$ nodes, and she constructs a new tree $(\dots((A \circ A) \circ A) \dots \circ A) \circ A$ (a total of $k$ copies of $A$). Clearly, this tree has $n^k$ nodes. She wants to know the sum of distances between all $\frac{n^k(n^k-1)}{2}$ pairs of nodes. Since this number is very large, you only need to output the value modulo $998244353$.
Input
The first line contains four positive integers $n, k, S, T$, representing the number of nodes in the double-rooted tree $A$, the number of $A$ trees multiplied together (i.e., $k$ in the problem description), and the indices of the root node and anti-root node in tree $A$, respectively.
The next $n-1$ lines each contain two integers $x, y$, representing an edge in $A$. It is guaranteed that the input is a tree.
Output
A single non-negative integer representing the sum of distances between all pairs of nodes.
Examples
Input 1
4 1 1 4 1 2 1 3 2 4
Output 1
10
Input 2
4 2 1 4 1 2 1 3 2 4
Output 2
488
Subtasks
| Subtask | $n$ | $k$ | Special Properties | Score |
|---|---|---|---|---|
| 1 | $\le 100$ | $= 1$ | None | 5 |
| 2 | $\le 3000$ | $\le 10$ | None | 10 |
| 3 | $\le 10^5$ | $\le 10$ | $n^k \le 10^6$ | 15 |
| 4 | $\le 1000$ | $\le 1000$ | None | 20 |
| 5 | $\le 10^5$ | $\le 10^9$ | $S = T$ | 10 |
| 6 | $\le 10^5$ | $\le 10^9$ | Tree is a chain, $S$ and $T$ are at the ends | 10 |
| 7 | $\le 10^5$ | $\le 10^9$ | None | 30 |
For all data, $1 \le S, T, x, y \le n$.
Note
A double-rooted tree is defined as a tree with two special nodes: a root node $S$ and an anti-root node $T$. The product $A \circ B$ of two double-rooted trees $A$ and $B$ is defined as follows:
- The tree $A \circ B$ has $n_A n_B$ nodes ($n_A, n_B$ denote the number of nodes in the two trees respectively), represented by pairs $(i, j)$, where $1 \le i \le n_A, 1 \le j \le n_B$.
- For all $1 \le u \le n_A$ and $1 \le v, w \le n_B$, if $v$ and $w$ are adjacent in $B$, then $(u, v)$ and $(u, w)$ are adjacent in $A \circ B$.
- For all $1 \le u, v \le n_A$, if $u$ is the parent of $v$ in $A$ (i.e., $u$ is adjacent to $v$ and is closer to $S_A$), then $(u, T_B)$ and $(v, S_B)$ are adjacent in $A \circ B$.
- The root node of $A \circ B$ is $(S_A, S_B)$, and the anti-root node is $(T_A, T_B)$.
Figure 1: As shown, this illustrates the structure of three trees $A, B, A \circ B$ in one case. The root of each tree is represented by an inverted triangle $\nabla$ shape, and the anti-root is represented by a $\triangle$ shape.