[ARC176] F - Colorful Star

F - Colorful Star

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 1000 分

题面

有一棵包含 个顶点编号从 到 的树。第 条边 () 连接顶点 和 。

初始时，顶点 被着以 的颜色。你可以执行以下操作零次或多次：

• 选择两个由一条边连接的顶点 和 。重绘顶点 的颜色为顶点 的颜色。

求在进行操作后，模 ，可能的树的数量。
如果某个顶点的颜色不同，那么两棵树是不同的。

限制条件

---

输入

输入由标准输入给出，格式如下：

输出

输出答案。

---

输入样例 1

3 1

输出样例 1

42

一种可能的操作序列如下。包括此操作，总共有 种可能的最终树形态。

---

输入样例 2

4 2

输出样例 2

219100

---

输入样例 3

20 24

输出样例 3

984288778

---

输入样例 4

123456 112233

输出样例 4

764098676