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!

Input

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.

Output

Print a single integer — the number of valid ways to assign each vertex a value, modulo $998\,244\,353$.

见题面 Input 部分

见题面 Output 部分

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]$.