← 返回题目列表

Codeforces · 1109/D

D. 萨沙和图论中的有趣事实

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

有一次,在上课时,萨沙感到无聊,决定和他的朋友们聊天。突然,他看到了克法。既然我们可以没完没了地谈论Kefa,我们甚至不会开始这样做。谈话转向图表。科法答应萨沙,如果萨沙帮助科法数出美丽的树的数量,就告诉他一个有趣的图论事实。

在此任务中,树是一个带权连通图,由$$$n$$$个顶点和$$$n-1$$$边组成,边的权重是从$$$1$$$到$$$m$$$的整数。 Kefa 按如下方式确定一棵树的美度:他在树中找到他最喜欢的两个顶点——编号为 $$$a$$$ 和 $$$b$$$ 的顶点,并计算它们之间的距离。两个顶点 $$$x$$$ 和 $$$y$$$ 之间的距离是从 $$$x$$$ 到 $$$y$$$ 的简单路径上边的权重之和。如果两个顶点 $$$a$$$ 和 $$$b$$$ 之间的距离等于 $$$m$$$,那么这棵树就是美丽的。

萨沙喜欢图论,更喜欢有趣的事实,这就是他同意帮助科法的原因。幸运的是,Sasha 认识你,他是 Byteland 最好的程序员。帮助萨莎数出科法有多少棵美丽的树。如果两棵树中的一棵出现了一条边,而另一棵则没有出现,则认为这两棵树是不同的。 Edge 的重量很重要。

Kefa 警告 Sasha,漂亮的树可能太多了,所以只需对 $$$10^9 + 7$$$ 求模即可。

输入

第一行包含四个整数 $$$n$$$, $$$m$$$, $$$a$$$, $$$b$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le m \le 10^6$$$, $$$1 \le a, b \le n$$$, $$$a \neq b$$$) —树中的顶点数、一条边的最大权重和两个 Kefa 最喜欢的顶点。

输出

打印一个整数——美丽树的数量以 $$$10^9+7$$$ 为模。

示例

输入 #1

3 2 1 3

输出 #1

5

输入 #2

3 1 1 2

输出 #2

2

输入 #3

5 15 1 5

输出 #3

345444

注意

第一个示例中有 $$$5$$$ 美丽的树:

在第二个示例中,以下树木很漂亮: