Лара, проте не Крофт
Limits: 1 sec., 128 MiB
Мало мати гарний розум, головне — правильно ним користуватися.
Рене Декарт
Богдан працює в 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 балів, без додаткових обмежень.
Input
У першому рядку задано два цілих числа \(n\) та \(m\) — розмір перестановки та число, за модулем якого треба надати відповідь.
Output
В єдиному рядку виведіть одне число, що позначає мінімальну кількість драбин, яка може знадобитися гравцю, щоб повністю завершити гру Богдана, за модулем \(m\).
Constraints
\(1 \leq n \leq 10^6\)
\(2 \leq m \leq 10^9 + 7\)
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 2 10 | 3 |
| Input (stdin) | Output (stdout) |
|---|---|
| 3 7 | 5 |
Notes
У першому прикладі маємо дві можливі перестановки: [1, 2] та [2, 1]. Для першої знадобиться 2 драбини, для другої — 1. В результаті гравцю щонайменше знадобиться 2 + 1 = 3 драбини, а відповідь виводимо за модулем 10: 3 mod 10 = 3.
У другому прикладі маємо 6 можливих перестановок, для яких знадобиться 12 драбин, а відповідь виводимо за модулем 7: 12 mod 7 = 5.
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|