Игра с графом
(Время: 1 сек. Память: 16 Мб Сложность: 83%)
Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены n кружочков, помеченных числами от 1 до n. Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка a в кружочек b разрешено проводить, если выполнены два условия:
- еще нет стрелочки из a в b;
- нельзя дойти по стрелочкам из b в a.
Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).
Проигрывает тот, кто не может сделать ход. Петя решил написать программу, играющую в эту игру. Для этого он хочет сначала посчитать, сколько различных позиций может получиться на доске.
Входные данные
Входной файл INPUT.TXT содержит одно число n (1 ≤ n ≤ 100).
Выходные данные
В выходной файл OUTPUT.TXT выведите число возможных позиций без ведущих нулей.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 | 25 |
Примечание
Приведем все 25 возможных позиций для примера из условия:
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
