21422번 - Игра с графом 다국어

문제

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

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

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

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

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

입력

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

출력

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

제한

힌트

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