Everyone knows that the mathematical department of the Ural State University is a big family of N persons, 1, 2, 3, …, N years old respectively.

Once the dean of the department ordered a photo of his big family. There were to be present all the students of the department arranged in one row. At first the dean wanted to arrange them by their age starting from the youngest student, but than he decided that it would look unnatural. Than he advised to arrange the students as follows:

The dean decided that thereby the students would seem look as they were arranged by their ages (one can hardly see the difference in ages of 25 and 27 years old people). There exist several arrangements satisfying to the requirements. Photographer didn’t want to thwart dean’s desire and made the photos of all the possible mathematical department students’ arrangements.

There is the integer number N, 1 ≤ N ≤ 55.

the number of photos made by the photographer.

If N = 4 then there are following possible arrangements: (1,2,3,4), (1,2,4,3), (1,3,2,4) and (1,3,4,2).