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 | |
|
| 2 | |
|