Задача Кактусы

Описание

Вершинный кактус - это связанный неориентированный граф, в котором каждая вершина лежит не более чем на одном простом цикле.

В свою очередь, реберный кактус - это связанный неориентированный граф, в котором каждое ребро лежит не более чем на одном цикле. Отметим, что любой вершинный кактус является реберным, но не наоборот, пример реберного кактуса, который не является вершинным приведен на рисунке.

По заданному n найдите количество помеченных вершин и реберных кактусов с n вершинами. Выведите эти числа по модулю 10 ⁹ +7.

Формат входных данных

Входной файл содержит n. (1 <= n <= 50).

Формат выходных данных

Выходной файл должен содержать количество помеченных вершин и количество помеченных реберных кактусов с n вершинами, оба числа должны быть выведены по модулю 10 ⁹ +7.