有一次,在上课时,萨沙感到无聊,决定和他的朋友们聊天。突然,他看到了克法。既然我们可以没完没了地谈论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$$$ 美丽的树:
在第二个示例中,以下树木很漂亮: