Responding to the call of the main theme, everyone decided to fill the class with love. Now there are $n$ boys in the class.

If $a$ loves $b$, then this is equivalent to having a directed edge $a \to b$ between them. If the directed graph formed by these $n$ nodes is strongly connected, then the class is considered to be full of love.

Unfortunately, some bad things happened, and now every edge may be destroyed. As a messenger of love, I want to know in how many different ways edges can be destroyed such that the class is still full of love.

(In plain words: how many subsets of edges can be deleted so that the entire graph remains strongly connected?)

Input Format

The first line contains two integers $n$ and $m$, representing the number of boys in the class and the number of love relationships.

The next $m$ lines each contain two integers $a$ and $b$, meaning that boy $a$ loves boy $b$. It is guaranteed that $a \ne b$.

All boys are numbered from $1$ to $n$.

The same edge will not appear twice, but it is possible that $a$ loves $b$ and $b$ loves $a$; these are considered two different edges.

Output Format

Output a single integer, representing the answer modulo $10^9 + 7$.

Example

Example Input

5 15
4 3
4 2
2 5
2 1
1 2
5 1
3 2
4 1
1 4
5 4
3 4
5 3
2 3
1 5
3 1

Example Output

9390

Constraints

For $20%$ of the data: $n \le 5$.

For $50%$ of the data: $n \le 8$.

For $70%$ of the data: $n \le 10$.

For $100%$ of the data: $n \le 15$, $0 \le m \le n(n - 1)$.