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

Limits: 2 sec., 512 MiB

У Зеника з Марічкою на фермі є $n$ жеребців, пронумерованих від $1$ до $n$.

Фермери хочуть вишикувати деяких своїх коней у шеренгу.

Назвемо шеренгу з $k$ коней гарною, якщо всі коні в цій шерензі мають номери від $1$ до $k$ в будь-якому порядку.

Наприклад, шеренги $(2, 1, 3)$, $(1)$, $(4, 3, 2, 1)$ є гарними, а $(1, 2, 4, 5)$, $(47)$, $(3, 2)$ — ні.

Зеник та Марічка хочуть вибрати деяких своїх коней, та вишикувати їх у шеренгу. Порахуйте, будь ласка, скільки різних гарних шеренг вони можуть отримати. Дві шеренги вважаємо різними, якщо в них різна довжина, або на відповідних позиціях стоять коні з різними номерами. Оскільки ця кількість може бути дуже великою, виведіть остачу від її ділення на ціле число $m$.

Input

В одному рядку задано два цілі числа $n$ та $m$.

Output

Виведіть ціле число — остачу від ділення кількості різних гарних шеренг на $m$.

Constraints

$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 бали: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Samples

Input (stdin) сopy	Output (stdout) сopy
3 10	9

Input (stdin) сopy	Output (stdout) сopy
4 7	5

Input (stdin) сopy	Output (stdout) сopy
7 777	474

Notes

У першому прикладі $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$.