Известно, что проходы в здании Зингера представляют из себя что-то сложное и переплетенное. Определим k-здание Зингера как граф, построенный следующим образом. Возьмем полное бинарное дерево высоты k, и добавим ребра между каждой вершиной и всеми ее потомками, если таких ребер еще нет.
4-здание Зингера Посчитайте число непустых путей в k-здании Зингера, не проходящих дважды по одной вершине. Пути различны, если различается множество или порядок посещенных вершин. Так как ответ может быть большим, выведите остаток от деления ответа на 109 + 7.
В единственной строке находится одно целое число k (1 ≤ k ≤ 400).
Выведите одно число — ответ на задачу по модулю 109 + 7.
2
9
3
245
20
550384565
В первом примере есть 9 путей (вершины пронумерованы на рисунке ниже): 1, 2, 3, 1-2, 2-1, 1-3, 3-1, 2-1-3, 3-1-2.
2-здание Зингера
