Kaaleppi is running an illegal taxi service in the city. The city consists of n crossings and m one-way streets between them. Each evening, Kaaleppi drives through a route of two or more crossings that are connected by the streets.

Of course, Kaaleppi doesn't want that the police becomes aware of his business. For this reason, he always chooses a route that is not suspicious.

A route is suspicious if it contains a double cycle. A double cycle is a route of form x \rightarrow R \rightarrow x \rightarrow R \rightarrow x where x is a crossing and R is a route where each crossing is dictinct and other than x. Note that R may consist of only one crossing.

For example, the route 2 \rightarrow 3 \rightarrow 6 \rightarrow 4 \rightarrow 3 \rightarrow 6 \rightarrow 4 \rightarrow 3 \rightarrow 1 \rightarrow 6 is suspicious because we can choose x=3 and R=6 \rightarrow 4.

Your task is to calculate the number of possible routes for Kaaleppi, i.e., the number of routes that contain at least two crossings and are not suspicious.

Input

The first input line contains integers n and m: the number of crossings and the number of streets. The crossings are numbered 1,2,\ldots,n.

After this, there are m lines that describe the streets. Each line contains two integers a and b. This means that there is a one-way street from a to b.

Output

Output the number of possible routes modulo 10^9+7. If the number is infinite, output infinite.

Constraints

• 2 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le a, b \le n

Example

Input:

4 4
1 2
2 3
3 4
4 2

Output:

21

Input:

5 6
1 2
1 3
1 4
2 4
3 4
4 5

Output:

13

Input:

3 4
1 2
2 1
2 3
3 2

Output:

infinite