Problem C. Cthulhu spawn

Author:A. Zhuplev, A. Klenin, I. Tufanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Scientists of the Nearsea Institute of Underwater Mythology are researching the mythical creature called Cthulhu.

The creature is famous for producing many offspring known as Cthulhu spawn. Each spawn has a small round body with N radially protruding appendages. Each appendage is either a tentacle or a claw.

Two spawns are considered identical, if one of them can be rotated in such a way that the sequence of tentacles and claws will coincide with the other spawn.

For example, if we designate tentacle by "T" and claw by "C", spawns "TCTCCT" and "CCTTCT" are identical and different from spawns "TTTCCT" ad "CCTTTC".

You program must, for given N, calculate the total number of different spawns with N appendages.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single integer — number of different spawns.

Constraints

1 ≤ N ≤ 58

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
2
2
4
6

0.090s 0.010s 15