G. The Symbolic Tree
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kyoto University has a magnificent symbolic tree as its symbol tree.

Impressed by this symbolic tree, K-kun made a copy of it as a rooted tree with $$$N$$$ vertices.

The vertices of the tree are labeled $$$1,2,\dots,N$$$, the root of the tree is vertex $$$1$$$, and the $$$i$$$-th edge connects vertices $$$u_i$$$ and $$$v_i$$$.

Thinking that merely copying the tree would be uninteresting, K-kun writes a non-negative integer on each vertex of the tree so that the following conditions are satisfied.

Conditions

  • The integer written on the root is $$$K$$$.
  • For each vertex other than the root, the integer written on that vertex is at most the integer written on its parent.

Find the remainder when the number of possible ways to write integers on the vertices of the tree is divided by $$$998244353$$$.

Two ways of writing integers on the vertices are considered different if and only if there exists some vertex such that the integer written on that vertex is different.

Input

The first line contains integers $$$N,K$$$ separated by spaces. ( $$$2 \leq N \leq 3000, 1 \leq K \leq 10^9$$$ )

Each of the following $$$N-1$$$ lines contains integers $$$u_i,v_i$$$ separated by spaces, representing an edge of the tree.

Output

Output the answer modulo $$$998244353$$$.

Examples
Input
5 1
1 2
1 3
3 4
3 5
Output
10
Input
16 16
15 14
15 11
7 10
14 2
4 6
14 16
5 3
1 5
12 11
5 7
2 9
13 10
5 14
9 6
8 1
Output
623173536
Note

For the first example, the following $$$10$$$ assignments of integers to vertices $$$1,2,3,4,5$$$ satisfy the conditions.

  • $$$1,0,0,0,0$$$
  • $$$1,0,1,0,0$$$
  • $$$1,0,1,0,1$$$
  • $$$1,0,1,1,0$$$
  • $$$1,0,1,1,1$$$
  • $$$1,1,0,0,0$$$
  • $$$1,1,1,0,0$$$
  • $$$1,1,1,0,1$$$
  • $$$1,1,1,1,0$$$
  • $$$1,1,1,1,1$$$