G. Shohag Loves Pebaetime limit per test5 secondsmemory limit per test768 megabytesinputstandard inputoutputstandard outputShohag 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 $$$998\,244\,353$$$, of assignments such that following conditions are satisfied: For each pair $$$1 \le u \lt v \le n$$$, the least common multiple (LCM) of the values of the nodes in the unique simple path from $$$u$$$ to $$$v$$$ is not divisible by the number of nodes in the path. The greatest common divisor (GCD) of the values of all nodes from $$$1$$$ to $$$n$$$ is $$$1$$$. But this problem is too hard for Shohag to solve. As Shohag loves Pebae, he has to solve the problem. Please save Shohag!InputThe first line contains two space-separated integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le m \le 10^{9}$$$).Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) indicating there is an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.OutputPrint a single integer — the number of valid ways to assign each vertex a value, modulo $$$998\,244\,353$$$.ExamplesInput6 61 22 33 44 53 6Output2
Input2 51 2Output7
Input12 693 51 42 34 55 68 97 34 89 101 1112 1Output444144548
NoteIn 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]$$$.