G. Shohag 爱 Pebae

时间限制： 每个测试点 $5$ 秒
内存限制： $768$ MB

$Shohag$ 有一棵包含 $n$ 个节点的树。

$Pebae$ 有一个整数 $m$。她想给每个节点分配一个值 —— 从 $1$ 到 $m$ 的整数。于是她请 $Shohag$ 计算满足以下条件的赋值方案数，结果对 $998244353$ 取模：

$1$. 对于每一对节点 $1 \le u < v \le n$，从 $u$ 到 $v$ 的唯一简单路径上所有节点的值的最小公倍数（$LCM$）不能被该路径上的节点数整除。 $2$. 所有 $n$ 个节点的值的最大公约数（$GCD$）等于 $1$。

这个问题对 $Shohag$ 来说太难了。因为 $Shohag$ 爱 $Pebae$，他必须解决这个问题。请救救 $Shohag$！

输入
第一行包含两个用空格分隔的整数 $n$ 和 $m$（$2 \le n \le 10^6$，$1 \le m \le 10^9$）。
接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示节点 $u$ 和 $v$ 之间有一条边。保证给定的边构成一棵树。

输出
输出一个整数 —— 有效的赋值方案数，对 $998244353$ 取模。

示例

输入 1

6 6
1 2
2 3
3 4
4 5
3 6

输出 1

2

输入 2

2 5
1 2

输出 2

7

输入 3

12 69
3 5
1 4
2 3
4 5
5 6
8 9
7 3
4 8
9 10
1 11
12 1

输出 3

444144548

提示
在第一个样例中，有效的赋值是 $[1,1,1,1,1,1]$ 和 $[1,1,1,1,1,5]$。
在第二个样例中，有效的赋值是 $[1,1]$、$[1,3]$、$[1,5]$、$[3,1]$、$[3,5]$、$[5,1]$ 和 $[5,3]$。