G-Romantic Misletoe_牛客练习赛98

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\text{RM}$ 有什么含义呢？ $\text{Romantic Misletoe? Real Madrid? Random Memory?}$

槲寄生，是属于圣诞前夜的浪漫的花，代表希望和丰饶，也代表爱情。

但是这所代表的和这道题没有任何关系，做出这道题不保证你能度过甜蜜的圣诞，也不能保证你不能度过一个甜蜜的圣诞。不同的是，圣诞节的那天，作为圣诞礼物小 L 给你了一道题目。

小 L 在采购圣诞礼物的时候发现树很有意思。他定义一个 $n$ 个节点的槲寄生树为一个满足如下要求的树：树的每个节点带正整数点权，且满足儿子节点的点权不大于父亲节点的点权，且所有点权的最大公约数为 $1$ ，且点权都 $\in [1,m]$ 。形式化地，即设点权为 $d_i$ ，则满足 $\gcd(d_1,d_2,\dots,d_n)=1$ 且 $\forall i, 1\le d_i\le d_{fa_i}\le m$ 。其中，树的根节点为 $1$ 。

因为小 L 正在关注皇家马德里的消息，所以代替他的小 L 给你了一个有 $n$ 个节点的树。不同于小 L，她想知道有多少不同的安排权值的方案使得这个树变成一棵槲寄生树，以便确定是否够送人。因为小 L 的圣诞节还要陪小 L 过，所以你只需要输出方案数对 $10^9+7$ 取余的结果。

$2\le n\le 2000, 1\le m\le 3\times 10^7$ 。

输入描述:

第一行两个正整数 。

后面  行输入两个正整数 ，表示树上的一条边 。

输出描述:

一行，一个整数表示方案数。

示例1

输入

复制

输出

复制

示例2

输入

复制

2 4
1 2

输出

复制

示例3

输入

复制

3 5
1 2
1 3

输出

复制

备注:

对于  的数据，。