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 4 3 5
1 4 6
1 3 5
2 3 3

2

Explanation for Sample Input

The two solutions are and .

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

0

Explanation for Sample Input 2

There are no solutions to this system of equations