Counting Spanning Arborescences after Adding an Edge

Consider a maple leaf with \(n\) acupoints numbered from \(1\) to \(n\). There are several directed meridians connecting these acupoints forming a directed acyclic graph (DAG) known as the meridian graph. The numbering guarantees that acupoint \(1\) has no incoming meridians; hence, there exists at least one spanning tree (called the meridian tree) rooted at acupoint \(1\) that covers all \(n\) acupoints.

Now, a new meridian (edge) that is not present in the original graph is added. Note that two meridians connecting the same pair of acupoints in opposite directions are considered different, and the new meridian can even be a self‐loop (from a node to itself).

The new graph (the original meridian graph plus the extra meridian) might contain cycles. Your task is to count the number of spanning arborescences (spanning trees with directed edges such that there is a unique path from acupoint \(1\) to every other acupoint) in the new graph. Since the number might be huge, output the count modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \leq n \leq \text{?},\ 0 \leq m \leq \text{?})\) — the number of acupoints and the number of meridians in the original meridian graph.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) \((1 \leq u, v \leq n, u, v \text{ are integers})\) denoting a directed meridian from acupoint \(u\) to acupoint \(v\). Note: if \(u = v\), it is a self‐loop.

The last line contains two integers \(x\) and \(y\) representing the extra meridian added to the graph. It is guaranteed that this meridian is not already present in the original graph. (Remember that a meridian from \(x\) to \(y\) is considered different from a meridian from \(y\) to \(x\).)

outputFormat

Output a single integer — the number of spanning arborescences rooted at acupoint \(1\) in the new graph, modulo \(10^9+7\).

sample

1 0
1 1

1