题目描述

Cătălin 在拜访祖父母时，在车库里发现了一台 1970 年的 Nintendo 游戏机。幸运的是，这台游戏机里还有一个叫做 TreeGCD 的游戏。

游戏给出一棵包含 $N$ 个节点的树，以及一个整数 $M$。

你需要给每个节点赋一个 $1$ 到 $M$ 之间的整数，使得任意两个相邻节点上的数都不是互质数。也就是说，对于任意一条边 $(u,v)$，都必须满足：

请你计算满足条件的赋值方案数。答案需要对 $1000000007$ 取模。

输入格式

第一行包含两个整数 $N,M$。

接下来 $N-1$ 行，每行包含两个整数 $x,y$，表示树上节点 $x$ 与节点 $y$ 相邻。

输出格式

输出一个整数，表示满足条件的赋值方案数对 $1000000007$ 取模后的结果。

数据范围与约定

• $2\le N\le 100$；
• $2\le M\le 10000$。

由于 $N\ge 2$，树中每个节点至少通过路径与其它节点相连，而赋值为 $1$ 的节点与任意邻居的最大公约数都是 $1$，因此合法方案中实际上不会出现值 $1$。

子任务

样例 1

输入

2 6
1 2

输出

13

样例解释

可以给节点 $1,2$ 赋值的有序数对为：

共 $13$ 种。

样例 2

输入

5 6
5 3
3 1
5 4
3 2

输出

397

样例解释

答案为 $397$。

样例 3

输入

10 67
1 2
1 3
2 4
2 5
2 6
2 7
5 8
5 9
7 10

输出

534323877

样例解释

实际方案数为：

对 $1000000007$ 取模后得到：