{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eВам дано натуральное число \u003cstrong\u003en\u003c/strong\u003e ≤ \u003cstrong\u003e1000\u003c/strong\u003e и простое число \u003cstrong\u003ep\u003c/strong\u003e (\u003cstrong\u003e10^7\u003c/strong\u003e \u003c \u003cstrong\u003ep\u003c/strong\u003e \u003c \u003cstrong\u003e10^9\u003c/strong\u003e). Найдите количество корневых деревьев из вершин с непомеченными вершинами, имеющих нечетное число независимых множеств. Результат выведите по модулю \u003cstrong\u003ep\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003eДерево называется \u003cem\u003eкорневым с непомеченными вершинами\u003c/em\u003e, если какая-то его вершина зафиксирована как корень, а порядок сыновей для любой вершины не важен. То есть два дерева считаются равными, если они совпадают после некоторого переупорядочения некорневых вершин. Совсем формальное определение: два корневых дерева с непомеченными вершинами \u003cstrong\u003eT_1\u003c/strong\u003e и \u003cstrong\u003eT_2\u003c/strong\u003e равны, если существует взаимно однозначное отображение \u003cstrong\u003ef\u003c/strong\u003e из множества вершин дерева \u003cstrong\u003eT_1\u003c/strong\u003e на множество вершин дерева \u003cstrong\u003eT_2\u003c/strong\u003e, которое переводит корень \u003cstrong\u003eT_1\u003c/strong\u003e в корень \u003cstrong\u003eT_2\u003c/strong\u003e и для любого ребра (\u003cstrong\u003eu\u003c/strong\u003e, \u003cstrong\u003ev\u003c/strong\u003e) из \u003cstrong\u003eT_1\u003c/strong\u003e в \u003cstrong\u003eT_2\u003c/strong\u003e есть ребро (\u003cstrong\u003ef(u)\u003c/strong\u003e, \u003cstrong\u003ef(v)\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003eНекоторое множество вершин графа (возможно пустое) называется \u003cem\u003eнезависимым\u003c/em\u003e, если никакие две вершины этого множества не соединены ребром.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВ единственной строке входного файла заданы числа \u003cstrong\u003en\u003c/strong\u003e и \u003cstrong\u003ep\u003c/strong\u003e.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eВ единственную строку выходного файла выведите ответ на задачу.\u003c/p\u003e\n\n"}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1 176531359\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}