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

Умова Обговорення

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

2 секунди

64 мегабайти

Середня

Вам дано натуральне число $n$ (n \leq 1000) та просте число $p$ (10^7 < p < 10^9). Ваше завдання — визначити кількість укорінених дерев з немаркованими вершинами, які мають непарну кількість незалежних множин. Виведіть відповідь за модулем $p$ .

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

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

Вхідні дані

У вхідних даних один рядок з числами $n$ та $p$ .

Вихідні дані

Виведіть відповідь на задачу в одному рядку.

Приклади

Приклад 1

Loading

Loading

n \leq 1000

1 0^{7} < p < 1 0^{9}

T_{1}

T_{2}

T_{1}

T_{2}

T_{1}

T_{2}

T_{1}

(f (u), f (v))

T_{2}