Shohag Loves Pebae

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

Pebae 有一个整数 $ m $。 她想给每个节点赋一个值--一个从 $ 1 $ 到 $ m $ 的整数。 所以她要求 Shohag 计算出，模数为 $ 998,244,353 $ 的赋值中，满足以下条件的赋值个数：

• 对于每一对 $ 1 \le u \lt v \le n $ ，从 $ u $ 到 $ v $ 的唯一简单路径中节点值的 最小公倍数 (LCM) 不能被路径中的节点数整除。
• 从 $ 1 $ 到 $ 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 $ 之间有一条边。 保证给定的边构成一棵树。

输出一个整数，为每个顶点赋值的有效方式的数量，数过大时要 $\bmod 998,244,353 $ 。

样例 #1

样例输入 #1

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

样例输出 #1

2

样例 #2

样例输入 #2

2 5
1 2

样例输出 #2

7

样例 #3

样例输入 #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, 5] $ 。

样例二中，有效赋值是 $ [1, 1] $ , $ [1, 3] $ , $ [1, 5] $ , $ [3, 1] $ , $ [3, 5] $ , $ [5, 1] $ 和 $ [5, 3] $ 。