Ніч у бібліотеці
Одного разу влітку Вовочка проходив у шкільній бібліотеці "літню практику": ремонтував підручники, допомагав бібліотекарям сортувати книги по відділам і тому подібне. У Вовочки дуже довгий ніс, який він завжди суне куди не слід, і бібліотечні книги не стали виключенням.
У одній з книг він побачив наступне:
… яка позначається 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.