Claire is secretly a fan of eroge. When she thinks nobody is looking, she boots up her laptop and starts playing...

We can model an eroge as a directed acyclic graph (DAG) with edges with vertices numbered from to . Each vertex is a choice point. Choice points are connected by edges, each taking up exactly 1 unit of time to advance.

Claire would like to play through all possible routes of her eroge. She may start at any choice point that does not have any other choice point leading to it. Help her compute the total time needed to play through the whole game!

In other words, you should compute the sum of the lengths of all paths from a vertex with indegree 0 to a vertex with outdegree 0. It is possible for the graph to have duplicate edges. If there are any isolated choice points (indegree and outdegree both 0), you should treat them as if they would be finished instantly.

#### Input Specification

The first line will have and separated by a single space, the number of vertices and edges, respectively.

The next lines will have a pair , separated by a single space, denoting a directed edge from to .

#### Output Specification

The first and only line of output should have the answer **modulo** , as this number can otherwise be very large.

#### Constraints

#### Sample Input 1

```
3 6
1 2
1 2
1 2
1 2
1 2
2 3
```

#### Sample Output 1

`10`

#### Sample Input 2

```
8 14
1 3
1 4
1 5
2 3
2 4
2 5
3 6
3 7
4 6
4 7
5 6
5 7
6 8
6 8
```

#### Sample Output 2

`48`

## Comments

This problem made me google "eroge" and had to clear my search history

This comment is hidden due to too much negative feedback. Click here to view it.

Missing space before .

parents thought it was porn....

What image? Oh wait I adblocked it.

It's from Seirei Tsukai no Blade Dance, which is

supposedto be 13+.Eh, why your parents are so suspicious of you? In that case, you should not solve questions like Rabbit/Cat/Dog girls.