eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Ніч у бібліотеці

Ніч у бібліотеці

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Одного разу влітку Вовочка проходив у шкільній бібліотеці "літню практику": ремонтував підручники, допомагав бібліотекарям сортувати книги по відділам і тому подібне. У Вовочки дуже довгий ніс, який він завжди суне куди не слід, і бібліотечні книги не стали виключенням.

У одній з книг він побачив наступне:

… яка позначається D(M) — кососиметрична полілінійна нормована функція стовбців квадратної матриці, тобто:

1. Якщо поміняти місцями два стовбці матриці, її значення міняє знак:

2. Якщо один зі стовбців матриці є лінійною комбінацією двох векторів, то лінійну комбінацію можна винести:

3. Для одиничної матриці вона дорівнює одиниці:

Доведемо, що така функція єдина:

… (Вовочка читає книги уривками) …

… наприклад, методом виключення Гауса.

… (іноді зовсім маленькими) …

… матриця X є добутком стовбця u на рядок v, тобто:

Вовочку дуже зацікавило те, що він прочитав. Оскільки Вовочка захоплюється олімпіадним програмуванням (тобто зависає на сайті "Кодефорсес"), то матриці і вектори йому не страшні. Проте з математикою у нього туго.

Він хоче порахувати значення описаної кососиметричної полілінійної нормованої функції D для матриці X, визначеної у отанньому уривку. Для простоти усі елементи векторів u та v є цілими числами. Щось підказує Вовочці, що відповідь також буде цілою. Ну а оскільки є підозри, що відповідь може бути дуже великою, то Вовочка хоче навчитись знаходити його по модулю простого числа P (просто так прийнято).

Допоможіть Вовочці розв'зати задачу. Інакше спам на вищезгаданому сайті забезпечено.

Вхідні дані

Перший рядок містить два цілих числа N та P (1N100, 2P2·10^9). Гарантується, що P — просте число. Другий рядок містить N цілих чисел u_1, u_2, …, u_n — елементи вектора-стовбця u, а третій рядок містить N цілих чисел v_1, v_2, …, v_n — елементи вектора-рядка v (0u_i, v_j < P).

Вихідні дані

Потрібно вивести одне ціле число: значення D(X) по модулю P. Число повинно бути невід'ємним і строго меншим, ніж P.

Приклад

Вхідні дані #1
3 11
0 7 8
10 5 3
Вихідні дані #1
0
Джерело Очний тур XIII Відкритої Всесибірської олімпіади з програмування імені І.В. Поттосіна