## DMOPC '19 Contest 1 P3 - Simple Math

View as PDF

Points: 12
Time limit: 5.0s
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 variables, . He then writes equations, the -th of which being the equation where . Believing that simply finding a solution to this problem would be too easy, he instead wants to find how many solutions of exist if he constrains each of the to be a positive integer less than or equal to . Since this number might be very large, he would be satisfied with this number modulo .

#### Constraints

There is at most solution.

#### Input Specification

The first line contains three space-separated integers, , , and .
lines follow, the -th of which contains three space-separated integers, , , and .

#### Output Specification

Output one line containing one integer, the number of solutions to the system modulo

#### Sample Input

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

#### Sample Output

2

#### Explanation for Sample Input

The two solutions are and .

#### Sample Input 2

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

#### Sample Output 2

0

#### Explanation for Sample Input 2

There are no solutions to this system of equations