Claire Elstein

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 1\,000\,000\,007 (= 10^9+7), as this number can otherwise be very large.


2 \le N \le 100\,000

1 \le M \le 500\,000

Sample Input 1

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

Sample Output 1


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



  • 22
    ManchurioX  commented on Jan. 11, 2020, 4:10 p.m.

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

  • -6
    jadhav  commented on July 20, 2019, 3:35 a.m.

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

  • 4
    Kirito  commented on Sept. 9, 2016, 5:40 p.m.

    Missing space before 1000000007(=10^9+7).

  • 48
    jimgao  commented on April 2, 2016, 3:10 p.m.

    parents thought it was porn....

    • 8
      quantum  commented on April 3, 2016, 5:31 p.m.

      What image? Oh wait I adblocked it.

    • 13
      Superoswald  commented on April 3, 2016, 5:25 p.m.

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

    • 66
      bruce  commented on April 3, 2016, 10:44 a.m.

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