STNBD P2 - Claire Elstein

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M
Author:
FatalEagle
Problem type

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 M edges with vertices numbered from 1 to N. 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 N and M separated by a single space, the number of vertices and edges, respectively.

The next M lines will have a pair i, j (i<j) separated by a single space, denoting a directed edge from i to j.

Output Specification

The first and only line of output should have the answer modulo 1000000007 (=109+7), as this number can otherwise be very large.

Constraints

2≤N≤100000

1≤M≤500000

Sample Input 1

Copy
3 6
1 2
1 2
1 2
1 2
1 2
2 3

Sample Output 1

Copy
10

Sample Input 2

Copy
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

Copy
48

Comments


  • 37
    ManchurioX  commented on Jan. 11, 2020, 9:10 p.m.

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


  • 63
    jimgao  commented on April 2, 2016, 7:10 p.m.

    parents thought it was porn....


    • 13
      quantum  commented on April 3, 2016, 9:31 p.m.

      What image? Oh wait I adblocked it.


    • 18
      Superoswald  commented on April 3, 2016, 9:25 p.m.

      It's from Seirei Tsukai no Blade Dance, which is supposed to be 13+.


    • 90
      bruce  commented on April 3, 2016, 2:44 p.m.

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