Лара, проте не Крофт

Обмеження: 1 сек., 128 МіБ

Богдан працює в GameDev компанії на посаді геймдизайнера, і до нього прийшла цікава ідея для майбутньої гри в жанрі “Головоломка”.

Ігровий світ складається з \(n!\) рівнів, кожен з яких є деякою унікальною перестановкою стовпів попарно різної висоти. Іншими словами, кожен рівень можна описати як перестановку стовпів висотами від 1 до \(n\). Гравець вміє падати вниз без отримання шкоди, але щоб забратися вверх йому потрібно використати драбину, кількість яких лімітована. Гравець починає гру з найпершого стовпа (висоти 0) і має досягнути останнього, рухаючись від першого стовпа до другого, від другого до третього і так далі.

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

Перестановкою називаємо послідовність довжини \(n\) цілих чисел від 1 до \(n\), в якій всі числа зустрічаються рівно 1 раз. Наприклад, [1], [4, 3, 5, 1, 2], [3, 2, 1] - перестановки, а [1,1], [4, 3, 1], [2, 3, 4] - ні.

Блоки тестів

• Блок 1: 5 балів, \(n \leq 5\), \(m > 10^3\).

• Блок 2: 5 балів, \(n \leq 10^6\), \(m \leq \max{(2,n)}\).

• Блок 3: 15 балів, \(n \leq 100\), \(m\) без обмежень.

• Блок 4: 35 балів, \(n \leq 10^4\), \(m\) без обмежень.

• Блок 5: 40 балів, без додаткових обмежень.

Вхідні дані

У першому рядку задано два цілих числа \(n\) та \(m\) — розмір перестановки та число, за модулем якого треба надати відповідь.

Вихідні дані

В єдиному рядку виведіть одне число, що позначає мінімальну кількість драбин, яка може знадобитися гравцю, щоб повністю завершити гру Богдана, за модулем \(m\).

Обмеження

\(1 \leq n \leq 10^6\)

\(2 \leq m \leq 10^9 + 7\)

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 10	3

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 7	5

Примітки

У першому прикладі маємо дві можливі перестановки: [1, 2] та [2, 1]. Для першої знадобиться 2 драбини, для другої — 1. В результаті гравцю щонайменше знадобиться 2 + 1 = 3 драбини, а відповідь виводимо за модулем 10: 3 mod 10 = 3.

У другому прикладі маємо 6 можливих перестановок, для яких знадобиться 12 драбин, а відповідь виводимо за модулем 7: 12 mod 7 = 5.