Для всех корневых деревьев с $n$ узлами найдите сумму их высот. Ответ выведите по модулю $p$.

Высота дерева определяется как длина самого длинного простого пути, начинающегося в корне.

Два корневых дерева считаются равными тогда и только тогда, когда у них одинаковое количество детей у корня, а соответствующие поддеревья (слева направо) также равны.

Входные данные

Вход содержит два целых числа $n$ и $p$.

Выходные данные

Выведите сумму высот всех корневых деревьев с $n$ узлами по модулю $p$.

Примеры

Пример 1

Входные данные

4 998244353

Выходные данные

10

Примечание к примеру 1

Для $n=4$:

• Существует $1$ дерево высоты $1$: корень имеет $3$ детей, каждый из которых — лист.
• Существует $3$ дерева высоты $2$:
  • Один ребенок, у которого есть два своих ребенка.
  • Два ребенка, один из которых — лист. Это дает $2$ варианта, так как порядок детей имеет значение (первый ребенок — лист или второй ребенок — лист).
• Существует $1$ дерево высоты $3$: путь длины $3$ (цепь).

Пример 2

Входные данные

10 998244353

Выходные данные

19838

Пример 3

Входные данные

514 998244353

Выходные данные

867876856

Подзадачи

Для первых $20\%$ данных $n\le 50$.

Для первых $40\%$ данных $n\le 400$.

Для первых $60\%$ данных $n\le 1000, p = 998244353$.

Для первых $80\%$ данных $n\le 2000$.

Для $100\%$ данных $1\le n\le 10^5, 9\times 10^8 \le p\le 1.01 \times 10^9$, где $p$ — простое число.