Sasha and Interesting Fact from Graph Theory
Contest: Codeforces Round 539 (Div. 1)
Difficulty rating: 2400
Tags: brute force, combinatorics, dp, math, trees

Once, during a lesson, Sasha got bored and decided to talk with his friends. Suddenly, he saw Kefa. Since we can talk endlessly about Kefa, we won't even start doing that. The conversation turned to graphs. Kefa promised Sasha to tell him about one interesting fact from graph theory if Sasha helps Kefa to count the number of beautiful trees.

In this task, a tree is a weighted connected graph, consisting of $$$n$$$ vertices and $$$n-1$$$ edges, and weights of edges are integers from $$$1$$$ to $$$m$$$. Kefa determines the beauty of a tree as follows: he finds in the tree his two favorite vertices — vertices with numbers $$$a$$$ and $$$b$$$, and counts the distance between them. The distance between two vertices $$$x$$$ and $$$y$$$ is the sum of weights of edges on the simple path from $$$x$$$ to $$$y$$$. If the distance between two vertices $$$a$$$ and $$$b$$$ is equal to $$$m$$$, then the tree is beautiful.

Sasha likes graph theory, and even more, Sasha likes interesting facts, that's why he agreed to help Kefa. Luckily, Sasha is familiar with you the best programmer in Byteland. Help Sasha to count the number of beautiful trees for Kefa. Two trees are considered to be distinct if there is an edge that occurs in one of them and doesn't occur in the other one. Edge's weight matters.

Kefa warned Sasha, that there can be too many beautiful trees, so it will be enough to count the number modulo $$$10^9 + 7$$$.

Input format:
The first line contains four integers $$$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$$$) — the number of vertices in the tree, the maximum weight of an edge and two Kefa's favorite vertices.

Output format:
Print one integer — the number of beautiful trees modulo $$$10^9+7$$$.

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
There are $$$5$$$ beautiful trees in the first example:

In the second example the following trees are beautiful:

Example input:
3 2 1 3

Example output:
5

Example input:
3 1 1 2

Example output:
2

Editorial:
Let's fix $$$edges$$$  — the number of edges on the path between $$$a$$$ and $$$b$$$. Then on this path there are $$$edges-1$$$ vertices between $$$a$$$ and $$$b$$$, and they can be choosen in $$$A(n - 2, edges - 1)$$$ ways. The amount of ways to place numbers on edges in such a way, that their sum is equal to $$$m$$$, is $$$\binom{m-1}{edges-1}$$$ (stars and bars method). If an edge doesn't belong to out path, then doesn't metter what number is written on it, so we can multiply answer by $$$m^{n-edges-1}$$$. Now, we want to form a forest from remaining $$$n-edges-1$$$ vertices and to hang it to any of $$$edges + 1$$$ vertexes from our path. According to one of generalizations of Cayley's formula, number of forsests of $$$x$$$ vertices, where vertices $$$1,2, \ldots, y$$$ belong to different trees is $$$f(x, y) = y \cdot x^{x - y - 1}$$$. So for fixed $$$edges$$$ we got the formula $$$trees(edges) = A(n - 2, edges - 1) \cdot f(n, edges + 1) \cdot \binom{m - 1}{edges - 1} \cdot m^{n - edges - 1}$$$
Complexity is $$$O((n + m) \cdot log(mod))$$$ or $$$O(n + m)$$$, in case you precompute all powers, factorials and thier inverse in linear time.