386. Happy Birthday, Jedi Knight!
Time limit per test: 0.25
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Jedi Knight has sneaked into the new model of Death Star. He is searching for very important enemy documents.
For each document he finds he will get a certain amount of money from the Jedi Council.
A new model of Death Star has the form of an
ndimensional parallelepiped.
Its edges are parallel to vectors
v_{1},...,
v_{n} with integer coordinates
and have the lengths equal to lengths of the corresponding vectors.
There is one document located in every integer point inside
or on the border of the Death Star.
If for any
k (0 ≤
k ≤
n) a document is inside some
kdimensional
facet of the parallelepiped, but either
k = 0 or it is not inside
any (
k1)dimensional facet, then its price is 2
^{k}.
Your task is to calculate the total amount of money Jedi can earn if he gets all the documents on
the Death Star. The answer can be enormous, but Jedi isn't afraid of this fact, so you should output it modulo prime number
p.
Input
The first line of the input file contains numbers
n and
p (2 ≤
n ≤ 50,
).
The next
n lines contain description of vectors
v_{i}.
Each of these lines contains
n integer numbers
a_{ij} (0 ≤
a_{ij} ≤
p1) — coordinates of the vector
v_{i}.
It is guaranteed that these vectors are linearly independent.
Output
Output must contain one number — the answer modulo
p.
Example(s)
sample input

sample output

2 43
1 0
0 1

4
