Игра с графом
Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены n кружочков, помеченных числами от 1 до n. Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек b разрешено проводить, если выполнены два условия:
ещё нет стрелочки из a в b;
нельзя дойти по стрелочкам из b в a.
Например, в позиции слева можно поставить одну из трёх стрелочек (стрелки показаны справа).
Проигрывает тот, кто не может сделать ход.
Петя решил написать программу, играющую в эту игру. Для этого он хочет сначала посчитать, сколько различных позиций может получиться на листочке.
Приведём все 25 позиций из условия.
Входные данные
Одно целое число n (1 ≤ n ≤ 100).
Выходные данные
Выведите количество возможных позиций без ведущих нулей.