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

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 в этой системе вычетов, и только вы сумеете ему в этом помочь.