← 返回题目列表

Codeforces · 2039/G

G. Shohag 爱 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,他必须解决这个问题。请救救肖哈格!

输入

第一行包含两个空格分隔的整数 $$$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]$$$。