CF2039G Shohag Loves Pebae

# Shohag Loves Pebae Shohag 有一棵有 $ n $ 个节点的树。 Pebae 有一个整数 $ m $。 她想给每个节点赋一个值--一个从 $ 1 $ 到 $ m $ 的整数。 所以她要求 Shohag 计算出，模数为 $ 998\,244\,353 $ 的赋值中，满足以下条件的赋值个数： - 对于每一对 $ 1 \le u \lt v \le n $ ，从 $ u $ 到 $ v $ 的唯一简单路径中节点值的 [最小公倍数 (LCM)](https://en.wikipedia.org/wiki/Least_common_multiple) 不能被路径中的节点数整除。 - 从 $ 1 $ 到 $ n $ 的所有节点值的[最大公约数（GCD）](https://en.wikipedia.org/wiki/Greatest_common_divisor) 是 $ 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] $ 。