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