## Problem C. Cthulhu spawn ≡

• problems
 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.

1 ≤ N ≤ 58

### Sample tests

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

0.140s 0.049s 15