Для всех корневых деревьев с $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$ — простое число.