Внутривузовские олимпиады/1-6 курсы/ТУСУР 2016


9. Кто определяет определитель?

Автор задачи: Соловьёв Виктор
Источник: Первый внутривузовский тур Региональной студенческой предметной олимпиады по программированию 13 марта 2016
Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Сегодня Дмитрий познакомился с удивительной вещью — модульной арифметикой. Знакомство это началось с записи

a ≡ b(mod m),

которая читается "a сравнимо с b по модулю m" и означает, что a и b дают при делении на m одинаковые остатки.

Так например

9 ≡ 2(mod7),

2 + 2 ≡ 1(mod3),

3 + 5 ≡ 0(mod4),

-1 ≡ 6(mod7).

Сама по себе модульная арифметика показалась Дмитрию не очень весёлой штукой, поэтому он сразу же перешёл к изучению систем вычетов. Выбранная им система вычетов по модулю m содержит только числа от 0 до m - 1 включительно. Результаты всех арифметических операций над элементами этой системы заменяются их остатками от деления на m, благодаря чему результат так же всегда принадлежит системе вычетов. Так например в 7-арифметике

1 + 2 + 3 = 6,

4 + 5 = 2,

6 * 6 = 1.

Дмитрий обнаружил, что большинство свойств обычной арифметики остаются справедливыми и в системе вычетов: например от перестановки слагаемых не меняется сумма, а от перестановки множителей — произведение.

В выбранной Диме системе вычетов нет отрицательных чисел, однако для любых двух чисел может быть найдена разность. Так, например, в 7-арифметике справедливо соотношение

1 - 5 = 3,

поскольку 3 + 5 = 1.

Интереснее оказалась ситуация с делением, которого в модульной арифметике попросту нет. Несмотря на это, для некоторых элементов могут быть найдены обратные к ним. Элемент b называется обратным к элементу a, если справедливо

a * b ≡ 1(mod m),

Так например обратным к элементу 3 в 7-арифметике будет элемент 5. То есть

3-1 ≡ 5(mod7),

Деление, таким образом, можно заменить умножением на обратный элемент, то есть вместо операции a / b использовать a * b- 1. Дмитрий выяснил, что если основание системы — простое число, то у любого ненулевого элемента в системе вычетов имеется обратный.

Разобравшись со всем этим, Дмитрий решил взяться за задачу посложнее. У него есть квадратная матрица A размерности n, элементы которой принадлежат системе вычетов по модулю m. Он хочет найти определитель матрицы A в этой системе вычетов, и только вы сумеете ему в этом помочь.

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

Первая строка входных данных содержит одно простое число m — основание модульной арифметики (2 ≤ m ≤ 1009).

Вторая строка содержит одно натуральное число n — размерность квадратной матрицы A (2 ≤ n ≤ 25).

Следующие n строк содержат по n целых чисел ai, j — элементы матрицы A (0 ≤ ai, j < m).

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

Вывести одно целое число от 0 до m - 1 — определитель матрицы A.

Примеры
Стандартный вводСтандартный вывод
5
2
4 2
0 3
2
11
3
1 2 3
4 5 6
7 8 9
0