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,他必须解决这个问题。请救救肖哈格!
输入
第一行包含两个空格分隔的整数 $$$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$$$ 之间有一条边。保证给定的边形成一棵树。
输出
打印单个整数 - 为每个顶点分配值的有效方法的数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #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]$$$。