Problem Statement

给定一棵 $n$ 个节点的树，你将这 $n$ 个节点依次染上 $m$ 种颜色之一。

我们称一棵树是好的，当且仅当所有同色点对距离的最小值介于 $[L,R]$ 之间。

你想知道一共有多少棵不同好的的树。这个数字可能很大，因而你只要求出这个值对 $10^9+7=1,000,000,007$ 取模的结果即可。

两棵树是不同的，当且仅当存在至少一个节点的颜色不同。

Input

第一行四个空格隔开的整数 $n,m,L,R$，分别表示树的点数，颜色数，以及最小值范围。

接下来 $n-1$ 行，每行两个空格隔开的整数 $u,v$，表示这棵树上有一条边连接 $u$ 与 $v$。

Output

一行一个整数，表示不同的树的个数对 $1,000,000,007$ 取模的结果。

Sample Input

3 3 1 2
1 2
2 3

Sample Output

21

Sample Explanation

除了三个点颜色互不相同的 $3!=6$ 种树之外，剩余的 $3^3-6=21$ 棵树都是可能出现的。

Constraints

对于所有数据，$1\le n\le 10^5$，$1\le m\le 10^9$，$1\le L\le R\lt n$。

• Subtask $1$（$20\%$）：$n,m\le 5$；
• Subtask $2$（$15\%$）：$L=R=n-1$；
• Subtask $3$（$15\%$）：$L=R=1$；
• Subtask $4$（$15\%$）：$n\le 5000$；
• Subtask $5$（$15\%$）：$L=R$；
• Subtask $6$（$20\%$）：无特殊限制。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$