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
In all subtasks,
,
Subtask 1 [10%]
Subtask 2 [20%]
There is at most solution.
Subtask 3 [70%]
No additional constraints.
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 1
4 3 5
1 4 6
1 3 5
2 3 3
Sample Output 1
2
Explanation for Sample Output 1
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 Output 2
There are no solutions to this system of equations.
Comments