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

Обмеження: 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\).