Shohag has a tree with n nodes.
Pebae has an integer m. She wants to assign each node a value — an integer from 1 to m. So she asks Shohag to count the number, modulo 998244353, of assignments such that following conditions are satisfied:
But this problem is too hard for Shohag to solve. As Shohag loves Pebae, he has to solve the problem. Please save Shohag!
The first line contains two space-separated integers n and m (2≤n≤106, 1≤m≤109).
Each of the next n−1 lines contains two integers u and v (1≤u,v≤n) indicating there is an edge between vertices u and v. It is guaranteed that the given edges form a tree.
Print a single integer — the number of valid ways to assign each vertex a value, modulo 998244353.
6 61 22 33 44 53 6
2
2 51 2
7
12 693 51 42 34 55 68 97 34 89 101 1112 1
444144548
In the first test case, the valid assignments are [1,1,1,1,1,1] and [1,1,1,1,1,5].
In the second test case, the valid assignments are [1,1], [1,3], [1,5], [3,1], [3,5], [5,1] and [5,3].
Name |
---|