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

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

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

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

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

Приведём все 25 позиций из условия.

Входные данные

Одно целое число n (1 ≤ n ≤ 100).

Выходные данные

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