STNBD P2 - Claire Elstein
View as PDFClaire 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 3Sample Output 1
10Sample 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 8Sample Output 2
48
Comments
This problem made me google "eroge" and had to clear my search history
parents thought it was porn....
What image? Oh wait I adblocked it.
It's from Seirei Tsukai no Blade Dance, which is supposed to be 13+.
Eh, why your parents are so suspicious of you? In that case, you should not solve questions like Rabbit/Cat/Dog girls.