DMOPC '19 Contest 1 P3 - Simple Math

View as PDF

Submit solution

Points: 12
Time limit: 2.5s
Memory limit: 128M

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

In math class, Bob is currently studying systems of linear equations. Being bored of his teacher's lectures, he decides to make a problem for himself. In his problem, he is trying to solve for the N variables, x_1,x_2,\ldots,x_N. He then writes M equations, the i-th of which being the equation x_{a_i}+x_{b_i}=c_i where a_i\neq b_i. Believing that simply finding a solution to this problem would be too easy, he instead wants to find how many solutions of (x_1,x_2,\ldots,x_N) exist if he constrains each of the x_i to be a positive integer less than or equal to K. Since this number might be very large, he would be satisfied with this number modulo 10^9+7.


In all subtasks,
2 \le N \le 300\,000
1 \le M \le 500\,000
1 \le K \le 10^9
1 \le a_i,b_i\le N, a_i\neq b_i
2 \le c_i \le 2K

Subtask 1 [10%]

1 \le K \le 5
1 \le N \le 10
1 \le M \le 20

Subtask 2 [20%]

There is at most 1 solution.

Subtask 3 [70%]

No additional constraints.

Input Specification

The first line contains three space-separated integers, N, M, and K.
M lines follow, the i-th of which contains three space-separated integers, a_i, b_i, and c_i.

Output Specification

Output one line containing one integer, the number of solutions (x_1,x_2,\ldots,x_N) to the system modulo 10^9+7

Sample Input

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

Sample Output


Explanation for Sample Input

The two solutions are (3,1,2,3) and (4,2,1,2).

Sample Input 2

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

Sample Output 2


Explanation for Sample Input 2

There are no solutions to this system of equations.


There are no comments at the moment.