题号：NC19788
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
魔方国有n座城市，编号为
。城市之间通过n-1条无向道路连接，形成一个树形结构。
澜澜打算在魔方国进行m次旅游，每次游览至少一座城市。为了方便，每次旅游游览的城市必须是连通的。此外，澜澜希望游览所有城市恰好一次。
澜澜想知道有多少种旅游方案满足条件，两个方案不同当且仅当存在某一次旅游游览了不同的城市。
澜澜不会数数，所以只好让你来帮他数方案。
澜澜打算在魔方国进行m次旅游，每次游览至少一座城市。为了方便，每次旅游游览的城市必须是连通的。此外，澜澜希望游览所有城市恰好一次。
澜澜想知道有多少种旅游方案满足条件，两个方案不同当且仅当存在某一次旅游游览了不同的城市。
澜澜不会数数，所以只好让你来帮他数方案。
输入描述:
第一行一个整数t表示数据组数 (1 ≤ t ≤ 100)。
每组数据第一行两个整数n,m，接下来n-1行每行两个整数ai,bi表示一条道路 (1≤ ai,bi≤ n)。
输出描述:
每组数据输出一行一个整数表示方案数对109+7取模的结果。