Гарна шеренга
Обмеження: 2 сек., 512 МіБ
У Зеника з Марічкою на фермі є nn жеребців, пронумерованих від 1 до n.
Фермери хочуть вишикувати деяких своїх коней у шеренгу.
Назвемо шеренгу з k коней гарною, якщо всі коні в цій шерензі мають номери від 1 до k в будь-якому порядку.
Наприклад, шеренги (2,1,3), (1), (4,3,2,1) є гарними, а (1,2,4,5), (47), (3,2) — ні.
Зеник та Марічка хочуть вибрати деяких своїх коней, та вишикувати їх у шеренгу. Порахуйте, будь ласка, скільки різних гарних шеренг вони можуть отримати. Дві шеренги вважаємо різними, якщо в них різна довжина, або на відповідних позиціях стоять коні з різними номерами. Оскільки ця кількість може бути дуже великою, виведіть остачу від її ділення на ціле число m.
Вхідні дані
В одному рядку задано два цілі числа n та m.
Вихідні дані
Виведіть ціле число — остачу від ділення кількості різних гарних шеренг на m.
Обмеження
1≤n≤109,
1≤m≤1000.
Оцінювання складається з таких блоків:
по 1 балу за кожен приклад з умови,
6 балів: m=1,
9 балів: n≤10,
23 бали: m=10,
17 балів: n≤1000,
42 бали: без додаткових обмежень.
Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 3 10 | 9 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 4 7 | 5 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 7 777 | 474 |
Примітки
У першому прикладі n=3,m=10. Зеник і Марічка можуть вибрати коней і вишикувати їх у шеренгу 15 способами:
(1) — гарна шеренга,
(1,2) — гарна шеренга,
(1,2,3) — гарна шеренга,
(1,3),
(1,3,2) — гарна шеренга,
(2),
(2,1) — гарна шеренга,
(2,1,3) — гарна шеренга,
(2,3),
(2,3,1) — гарна шеренга,
(3),
(3,1),
(3,1,2) — гарна шеренга,
(3,2),
(3,2,1) — гарна шеренга.
У дев’яти способах утворена шеренга є гарною. Відповідь — це остача від ділення 9 на 10, що дорівнює 9.
У другому прикладі n=4,m=7. Зеник з Марічкою можуть утворити 33 гарні шеренги. Відповідь — це остача від ділення 33 на 7, що дорівнює 5.