Дерева з непарною кількістю незалежних множин
Вам задано натуральне число n ≤ 1000 і просте число 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.
Вихідні дані
У єдиний рядок вихідного файлу виведіть відповідь до задачі.