Задачі
Планета
Планета
Обычные \textbf{n}-мерные котята живут в городах на необычной планете, которая представляет собой \textbf{n}-мерный параллелепипед в \textbf{n}-мерном пространстве. Рёбра этого параллелепипеда параллельны векторам \textbf{v_1}, ..., \textbf{v_n} с целыми координатами и их длина равна длине соответствующих векторов.
В каждой точке с целыми координатами внутри или на границе этой планеты находится по одному городу. Для каждого \textbf{k} (\textbf{0} ≤ \textbf{k} ≤ \textbf{n}) в городе живёт \textbf{2^k} котят, если он находится внутри некоторой \textbf{k}-мерной грани этого параллелепипеда, и, либо \textbf{k = 0}, либо город не находится внутри никакой (\textbf{k-1})-мерной грани этого параллелепипеда.
Требуется посчитать общее количество \textbf{n}-мерных котят, живущих на этой планете. Так как \textbf{n}-мерных котят может быть очень много, требуется вывести остаток от деления искомого количества на заданное простое число \textbf{p}.
\InputFile
Первая строка входного файла содержит числа \textbf{n} и \textbf{p} (\textbf{2} ≤ \textbf{n} ≤ \textbf{50}, \textbf{2} ≤ \textbf{p} ≤ \textbf{10007}). Следующие \textbf{n} строк содержат описания векторов \textbf{v_i}. В каждой из этих строк записано по \textbf{n} целых чисел \textbf{a_ij} (\textbf{0} ≤ \textbf{a_ij} < \textbf{p}) --- координаты вектора \textbf{v_i}. Гарантируется, что эти векторы линейно независимы.
\OutputFile
Выведите одно число --- остаток от деления искомого количества на \textbf{p}.
Вхідні дані #1
2 43 1 0 0 1
Вихідні дані #1
4