Дистанционный практикум по программированию

Кодовый дверной замок содержит N кнопок. Замок открывается, если нажата правильная последовательность комбинаций кнопок.

Комбинация кнопок состоит из одной или более кнопок, которые нужно нажать одновременно. Последовательность состоит из одной или более комбинаций. Если какая-то кнопка участвовала в одной из комбинаций, она не может быть использована в другой комбинации той же последовательности. В последовательности не обязательно использовать все кнопки замка. Например, для замка с 8 кнопками:

(1-2-3)(4)(7-8)

является допустимой последовательностью с тремя комбинациями (1-2-3), (4) и (7-8). Заметьте, что кнопки 5 и 6 не использованы в этой последовательности.

(1-2-3)(2-4)(5-6)

не является допустимой последовательностью, поскольку кнопка 2 присутствует в двух комбинациях — (1-2-3) и (2-4).

По заданному количеству кнопок N найдите количество допустимых последовательностей комбинаций кнопок кодового замка.

Входные данные. В первой строке входных данных находится число N (1  ≤   N   ≤  10) — количество кнопок в замке.

Выходные данные. Выведите одно число — количество последовательностей, возможных для замка с N кнопками.

Пример ввода

3

Пример вывода

25