DMOPC '19 Contest 1 P3 - Simple Math

View as PDF

Submit solution


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

Author:
Problem type

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, x1,x2,,xN. He then writes M equations, the i-th of which being the equation xai+xbi=ci where aibi. Believing that simply finding a solution to this problem would be too easy, he instead wants to find how many solutions of (x1,x2,,xN) exist if he constrains each of the xi 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 109+7.

Constraints

In all subtasks,
2N300000
1M500000
1K109
1ai,biN, aibi
2ci2K

Subtask 1 [10%]

1K5
1N10
1M20

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, ai, bi, and ci.

Output Specification

Output one line containing one integer, the number of solutions (x1,x2,,xN) to the system modulo 109+7.

Sample Input 1

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

Sample Output 1

Copy
2

Explanation for Sample Output 1

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

Sample Input 2

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

Sample Output 2

Copy
0

Explanation for Sample Output 2

There are no solutions to this system of equations.


Comments

There are no comments at the moment.