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 \le N \le 3000, 1 \le K \le 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
Sample Input 1
5 1 1 2 1 3 3 4 3 5
Sample Output 1
10
Sample Input 2
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
Sample Output 2
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$