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