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