Гарна шеренга

Обмеження: 2 сек., 512 МіБ

У Зеника з Марічкою на фермі є $n$ жеребців, пронумерованих від $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 \le n \le 10^9$,

$1 \le m \le 1000$.

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 6 балів: $m = 1$,

• 9 балів: $n \le 10$,

• 23 бали: $m = 10$,

• 17 балів: $n \le 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$.