eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Планета

Планета

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Обычные n-мерные котята живут в городах на необычной планете, которая представляет собой n-мерный параллелепипед в n-мерном пространстве. Рёбра этого параллелепипеда параллельны векторам v_1, ..., v_n с целыми координатами и их длина равна длине соответствующих векторов.

В каждой точке с целыми координатами внутри или на границе этой планеты находится по одному городу. Для каждого k (0kn) в городе живёт 2^k котят, если он находится внутри некоторой k-мерной грани этого параллелепипеда, и, либо k = 0, либо город не находится внутри никакой (k-1)-мерной грани этого параллелепипеда.

Требуется посчитать общее количество n-мерных котят, живущих на этой планете. Так как n-мерных котят может быть очень много, требуется вывести остаток от деления искомого количества на заданное простое число p.

Входные данные

Первая строка входного файла содержит числа n и p (2n50, 2p10007). Следующие n строк содержат описания векторов v_i. В каждой из этих строк записано по n целых чисел a_ij (0a_ij < p) — координаты вектора v_i. Гарантируется, что эти векторы линейно независимы.

Выходные данные

Выведите одно число — остаток от деления искомого количества на p.

Пример

Входные данные #1
2 43
1 0
0 1
Выходные данные #1
4
Источник III Международная Летняя школа программирования 2012 г. Севастополь