eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дерева з непарною кількістю незалежних множин

Дерева з непарною кількістю незалежних множин

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Вам задано натуральне число n1000 і просте число p (10^7 < p < 10^9). Знайдіть кількість кореневих дерев із вершин з непоміченими вершинами, які мають непарну кількість незалежних множин. Результат виведіть по модулю p.

Дерево називається кореневим з непоміченими вершинами, якщо якась його вершина зафікована як корінь, а порядок синів для довільної вершини не важливий. Тобто два дерева вважаються однаковими, якщо вони співпадають після деякого переупорядкування некореневих вершин. Зовсім формальне означення: два кореневих дерева з непоміченими вершинами T_1 і T_2 рівні, якщо існує взаємно однозначне відображення f з множини вершин дерева T_1 на множину вершин дерева T_2, яке переводить корінь T_1 у корінь T_2 і для довільного ребра (u, v) з T_1 у T_2 є ребро (f(u), f(v)).

Деяка множина вершин графа (можливо порожня) називається незалежною, якщо ніякі дві вершини цієї множини не з'єднані ребром.

Вхідні дані

У єдиному рядку вхідного файлу задано числа n і p.

Вихідні дані

У єдиний рядок вихідного файлу виведіть відповідь до задачі.

Приклад

Вхідні дані #1
1 176531359
Вихідні дані #1
0
Автор Антон Луньов
Джерело Зимова Школа, Харків 2011, День 6