Description

Assume there are $n$ acupoints on a maple leaf, numbered $1 \sim n$. Several directed veins connect these acupoints.

The acupoints and veins form a directed acyclic graph—called the vein graph (for example, Figure $1$). The numbering of the acupoints ensures that acupoint $1$ has no incoming veins from other acupoints, that is, acupoint $1$ only has outgoing veins. As the story above suggests, this directed acyclic graph contains a tree-shaped subgraph: a tree rooted at acupoint $1$ that spans all $n$ acupoints—called a vein-tree (for example, the trees in Figure $2$ and Figure $3$ are both vein-trees of the vein graph given by Figure $1$).

Note that there may be multiple vein-tree schemes in the vein graph. For example, Figure $2$ and Figure $3$ are two different vein-tree schemes for the vein graph in Figure $1$.

A formal definition of a vein-tree is as follows: a vein-tree rooted at acupoint $r$ consists of all $n$ acupoints and $(n-1)$ veins. There are no cycles in the vein-tree, nor self-loops. Moreover, for every acupoint $s$ on the leaf, there exists a unique vein path contained in the vein-tree such that starting from acupoint $r$ and following this path you can reach acupoint $s$.

Now we add one new vein, different from all existing veins, to the vein graph (note: veins connecting the same two acupoints but in opposite directions are considered different. For example, the vein from acupoint $3$ to $4$ is different from the vein from $4$ to $3$. Therefore, in Figure $1$, you cannot add a vein from $3$ to $4$, but you may add a vein from $4$ to $3$). This new vein may be a self-loop (for example, in Figure 1, a vein from $4$ to $4$ can be added).

After adding this new vein, cycles formed by veins may appear in the new vein graph. Please compute the number of vein-tree schemes rooted at acupoint $1$ in the new vein graph after adding this vein.

Since the number of schemes may be very large, output it modulo $(10^9+7)$.

Input Format

The first line contains four integers $n, m, x, y$, representing the number of acupoints on the leaf, the number of veins, and that the vein to be added goes from acupoint $x$ to acupoint $y$.

The next $m$ lines each contain two integers separated by a space, representing one existing vein.

In line $i$, the two integers are $u_i$ and $v_i$, meaning the $i$-th vein goes from acupoint $u_i$ to acupoint $v_i$.

Output Format

Output one line: the number of vein-tree schemes rooted at acupoint $1$ on the leaf after adding the vein from $x$ to $y$, modulo $(10^9+7)$.

4 4 4 3
1 2
1 3
2 4
3 2

3

Hint

For all testdata, it is guaranteed that:

• $1 \leq n \leq 100000$.
• $n - 1 \leq m \leq \min(200000, n(n - 1)/2)$.
• $1 \leq x, y, u_i, v_i \leq n$.

Fixed by Starrykiller.

Translated by ChatGPT 5