Equation Princess
By Daniel Bossle & Vinicius Coelho 
Brazil
By Daniel Bossle & Vinicius Coelho Brazil
Gertrude is a modern princess. Although she lives in a castle and is surrounded by employees who can give her anything she wants, she prefers to be independent and dispense with all those pampering. Her dream is to be able to leave the castle and live on her own, earning her own money and no one to disturb her. But her parents, very traditional, did not like her attitude and decided to get a prince to marry her. "Hopefully ending with this nonsense", they said. However, every suitor presented to her leaves in frustration. Although she does not know how to rime, Gertrude had the following condition to marry:
"For my hand to have, great mathematical knowledge needs to know
There is a lonely magic value k that does not want to be disturbed
If in a mod k linear equation system, the number of solutions unravel
With the wise and determined warrior I shall rejoice"
A prince from a kingdom so so close has come up with the solution but he does not know how to codify. Luckily, he found you and has asked for your help in this task.
The first line of the test case is given by three integers N, M (1 <= N, M <= 100) and K (2 <= K <109), where N is the number of equations, M is the number of variables, and K is the magic value, which is a prime number. The next line consists of N integers bi (0 <= bi < K), indicating the constant terms of the equations. The next N lines contain M integers aj (0 <= aj < K) representing the coefficients of the variables.
The output should contain a single integer containing the number of solutions for the system. Since this number can be very large, print only the rest of your division by 109 + 7.
| Input Sample | Output Sample |
|
2 2 3 |
3 |