Given a tree with $n$ nodes and a positive integer $m$, the weight of each node is chosen independently and uniformly at random from $[1, m]$.

Calculate the expected value of the maximum independent set of this tree, multiplied by $m^n$.

The result should be taken modulo $998244353$.

The maximum independent set of a tree with node weights $a_{1\dots n}$ is defined as $\max\limits_{S\subseteq \{1,2,\cdots,n\}} \left(\sum\limits_{i\in S} a_i\right)$, where $S$ must satisfy the condition that no two nodes in $S$ are connected by an edge.

Input

The first line contains two positive integers $n$ and $m$.

The next $n-1$ lines each contain two positive integers, representing an edge of the tree.

Output

Output a single non-negative integer representing the answer.

Examples

Input 1

3 2
1 2
1 3

Output 1

24

Note

For example, when the node weights are $[2, 1, 1]$, the maximum independent set is $2$, which can be achieved by choosing $\{1\}$ or $\{2, 3\}$.

Subtasks

For all test cases, $1\le n\le 2000$ and $1\le m\le 10^8$.

• Subtask 1 (11 pts): $n, m\le 5$.
• Subtask 2 (24 pts): $n, m\le 20$.
• Subtask 3 (13 pts): $n, m\le 500$.
• Subtask 4 (27 pts): $n\le 500$.
• Subtask 5 (25 pts): No additional constraints.