Деревья с нечётным числом независимых множеств
Вам дано натуральное число 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.
Выходные данные
В единственную строку выходного файла выведите ответ на задачу.