Ночь в библиотеке
Однажды летом Вовочка проходил в школьной библиотеке "летнюю практику": чинил учебники, помогал библиотекарям сортировать книги по отделам и тому подобное. У Вовочки очень длинный нос, который он вечно сует куда не следует, и библиотечные книги не стали исключением.
В одной из книг он увидел следующее:
… обозначаемый через D(M) — кососимметричная полилинейная нормированная функция столбцов квадратной матрицы, т.е.:
1. Если поменять местами два столбца матрицы, его значение меняет знак:
2. Если один из столбцов матрицы является линейной комбинацией двух векторов, то линейную комбинацию можно вынести:
3. Для единичной матрицы он равен единице:
Докажем, что такая функция единственна:
… (Вовочка читает книги обрывками) …
… например, методом исключения Гаусса.
… (иногда совсем маленькими) …
… матрица X является произведением столбца u на строку v, т.е.:
Вовочку очень заинтересовало то, что он прочитал. Поскольку Вовочка увлекается олимпиадным программированием (т.е. зависает на сайте "Кодефорсес"), то матрицы и векторы ему не страшны. Однако с математикой у него туго.
Он хочет посчитать значение описанной кососимметричной полилинейной нормированной функции D для матрицы X, определённой в последнем отрывке. Для простоты все элементы векторов u и v являются целыми числами. Что-то подсказывает Вовочке, что ответ также будет целым. Ну а поскольку есть подозрения, что ответ может быть очень большим, то Вовочка хочет научиться находить его по модулю простого числа P (просто так принято).
Помогите Вовочке решить задачу. Иначе спам на вышеупомянутом сайте обеспечен.
Входные данные
Первая строка содержит два целых числа N и P (1 ≤ N ≤ 100, 2 ≤ P ≤ 2·10^9). Гарантируется, что P — простое число. Вторая строка содержит N целых чисел u_1, u_2, …, u_n — элементы вектора-столбца u, а третья строка содержитN целых чисел v_1, v_2, …, v_n — элементы вектора-строки v (0 ≤ u_i, v_j < P).
Выходные данные
Требуется вывести одно целое число: значение D(X) по модулю P. Число должно быть неотрицательным и строго меньше, чем P.