시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Петя и Вася играют в очередную интересную игру. У них есть лист бумаги, на котором изображены $n$ кружочков, помеченных числами от $1$ до $n$. Участники по очереди рисуют стрелочки, соединяющие кружочки. При этом стрелочку из кружочка $a$ в кружочек $b$ разрешено проводить, если выполнены два условия:
Например, в позиции на рис. 1 можно поставить одну из трех стрелочек (рис. 2).
Рис. 1 | Рис. 2 |
Проигрывает тот, кто не может сделать ход.
Петя решил написать программу, играющую в эту игру. Для этого он хочет сначала посчитать, сколько различных позиций может получиться на доске.
Входной файл содержит одно число $n$ ($1\le n\le 100$).
Выведите в выходной файл число возможных позиций без ведущих нулей.
3
25
Приведем все 25 возможных позиций для примера из условия: