386. Happy Birthday, Jedi Knight!
Time limit per test: 0.25
Memory limit: 262144
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 n
Its edges are parallel to vectors v1
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
) a document is inside some k
facet of the parallelepiped, but either k
= 0 or it is not inside
-1)-dimensional facet, then its price is 2k
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
The first line of the input file contains numbers n
(2 ≤ n
The next n
lines contain description of vectors vi
Each of these lines contains n
integer numbers aij
(0 ≤ aij
-1) — coordinates of the vector vi
It is guaranteed that these vectors are linearly independent.
Output must contain one number — the answer modulo p