Игра с графом

Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены $n$ кружочков, помеченных числами от $1$ до $n$. Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка $a$ в кружочек $b$ разрешено проводить, если выполнены два условия:

1. еще нет стрелочки из $a$ в $b$;
2. нельзя дойти по стрелочкам из $b$ в $a$.

Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).

Рис. 1	Рис. 2

Проигрывает тот, кто не может сделать ход.

Петя решил написать программу, играющую в эту игру. Для этого он хочет сначала посчитать, сколько различных позиций может получиться на доске.

Входной файл содержит одно число $n$ ($1\le n\le 100$).

Выведите в выходной файл число возможных позиций без ведущих нулей.

Приведем все 25 возможных позиций для примера из условия: