Всем известно, что матмех — это одна большая семья численностью в N человек, возраст которых 1 год, 2 года, 3 года, …, N лет соответственно.

Однажды декан заказал фотографию своей большой «семьи». На фотографии должны присутствовать все студенты матмеха, и для этого они должны расположиться в один ряд. Сперва было решено расположить студентов по старшинству, начиная с самого младшего. Но фотограф сказал, что, возможно, на фото это будет выглядеть неестественно. Тогда декан посоветовал студентам расположиться так:

Декан решил, что на фотографии, таким образом, студенты будут все равно выглядеть будто расположенные по старшинству (ведь среди людей с возрастом, к примеру, 25 и 27 лет не так легко определить старшего). Способов такой посадки существует, понятно, несколько. Фотограф, ни в чём не переча декану, заснял все такие способы.

В единственной строке записано число N, 1 ≤ N ≤ 55.

Выведите количество фотографий всех студентов матмеха.

При N = 4 существуют следующие способы рассадки: (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2).