Author: | A. Zhuplev, A. Klenin, I. Tufanov | Time limit: | 1 sec | |
Input file: | input.txt | Memory limit: | 256 Mb | |
Output file: | output.txt |
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 contains a single integer N.
Output file must contain a single integer — number of different spawns.
1 ≤ N ≤ 58
No. | Input file (input.txt ) |
Output file (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|