F. Cycles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Trotles is given a set of $$$n$$$ nodes and wants to construct a functional graph where the in-degree and out-degree of each node is $$$1$$$. Luckily for him, he is already given the some of the edges. For the rest of the edges he randomly chooses a node with the out-degree $$$0$$$ and a node with in-degree $$$0$$$ (they can be the same node) and draw an edge from the first one to the second one. Calculate the expected number of cycles in the graph modulo $$$10^9 + 7$$$.

Input

The first line contain $$$n$$$ and $$$m$$$, the number of nodes and the number of given edges respectively. $$$1 \le m \le n \le 10^5$$$

The next $$$m$$$ lines contain two numbers $$$a$$$ and $$$b$$$ which means that there is an edge drawn between nodes $$$a$$$ and $$$b$$$. $$$1 \le a, b \le n$$$

It is guaranteed that the in-degree and out-degree of each node given in the test case will be less than or equal to $$$1$$$.

Output

Print a single integer representing the expected number of cycles.

If the number of cycles is $$$\frac{p}{q}$$$ then print $$$p \cdot q^{-1} \pmod {10^9 + 7}$$$.

Examples
Input
4 2
2 4
3 1
Output
500000005
Input
9 6
9 4
6 6
7 7
1 8
3 1
8 2
Output
833333343