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 (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! The 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. Print a single integer — the number of valid ways to assign each vertex a value, modulo (998\,244\,353). 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).