← 返回题目列表

Codeforces · 855/C

C. 赫尔加·赫奇帕奇的杯子

中文机器翻译题面 查看原题

哈利、罗恩和赫敏发现赫尔加·赫奇帕奇的杯子是一个魂器。通过与贝拉特里克斯·莱斯特兰奇的相遇,赫敏了解到这个杯子位于古灵阁巫师银行贝拉特里克斯家族的金库中。

巫师银行是一棵树的形式,共有 n 个金库,每个金库都有某种类型,用 1 到 m 之间的数字表示。树是没有环的无向连通图。

具有最高安全性的保管库是 k 类型,并且所有 k 类型的保管库都具有最高安全性。

最多可以有 x 个最高安全性的保管库。

此外,如果一个金库具有最高的安全性,则保证其相邻的金库不是最高的安全性,并且它们的类型保证小于 k。

哈利想要考虑每一种可能性,以便他能够轻松找到到达贝拉特里克斯金库的最佳路径。因此,你必须告诉他,考虑到古灵阁的树结构,为每个金库赋予满足上述条件的类型的可能方法有多少种。

输入

输入的第一行包含两个空格分隔的整数,n 和 m - 保险库的数量以及可能的不同保险库类型的数量。 (1≤n≤105,1≤m≤109)。

接下来的 n - 1 行中的每一行都包含两个空格分隔的整数 ui 和 vi (1 ≤ ui, vi ≤ n),表示第 i 条边,这表明两个金库 ui 和 vi 之间存在一条路径。保证给定的图是一棵树。

输入的最后一行包含两个整数 k 和 x (1 ≤ k ≤ m, 1 ≤ x ≤ 10),最高安全保险库的类型和最高安全保险库的最大可能数量。

输出

输出一个整数,即按照条件模 109 + 7 为每个库提供类型的方式数。

示例

输入 #1

4 2
1 2
2 3
1 4
1 2

输出 #1

1

输入 #2

3 3
1 2
1 3
2 1

输出 #2

13

输入 #3

3 1
1 2
1 3
1 1

输出 #3

0

注意

在测试用例 1 中,我们不能拥有任何最高安全性的保管库,因为其类型为 1,这意味着其相邻保管库的保管库类型必须小于 1,这是不允许的。因此,只有一种可能的组合,其中所有金库都具有类型 2。