Задачи
Деревья с нечётным числом независимых множеств
Деревья с нечётным числом независимых множеств
Вам дано натуральное число \textbf{n} ≤ \textbf{1000} и простое число \textbf{p} (\textbf{10^7} < \textbf{p} < \textbf{10^9}). Найдите количество корневых деревьев из вершин с непомеченными вершинами, имеющих нечетное число независимых множеств. Результат выведите по модулю \textbf{p}.
Дерево называется \textit{корневым с непомеченными вершинами}, если какая-то его вершина зафиксирована как корень, а порядок сыновей для любой вершины не важен. То есть два дерева считаются равными, если они совпадают после некоторого переупорядочения некорневых вершин. Совсем формальное определение: два корневых дерева с непомеченными вершинами \textbf{T_1} и \textbf{T_2} равны, если существует взаимно однозначное отображение \textbf{f} из множества вершин дерева \textbf{T_1} на множество вершин дерева \textbf{T_2}, которое переводит корень \textbf{T_1} в корень \textbf{T_2} и для любого ребра (\textbf{u}, \textbf{v}) из \textbf{T_1} в \textbf{T_2} есть ребро (\textbf{f(u)}, \textbf{f(v)}).
Некоторое множество вершин графа (возможно пустое) называется \textit{независимым}, если никакие две вершины этого множества не соединены ребром.
\InputFile
В единственной строке входного файла заданы числа \textbf{n} и \textbf{p}.
\OutputFile
В единственную строку выходного файла выведите ответ на задачу.
Входные данные #1
1 176531359
Выходные данные #1
0