Zoo#157
There are cages in the zoo, arranged in a row. Among the inhabitants are two monkeys, Khem and Sem. Khem and Sem used to be close friends and always sat in neighboring cages, but now they have quarreled and do not want to see each other. The zookeeper wants to resettle them according to their wishes but faces a problem. Khem and Sem are intelligent monkeys (each has finished eight grades!), and they want to know how many ways there are to place them so that their cages are not adjacent, with each in a different cage. Assume all cages are available, and the other animals are willing to move anywhere.
The zookeeper tried to count the possibilities but lost track somewhere near the hippos. Clearly, without your help, he will not manage!
The first line contains the number of cages (2 \le n \le 100).
Print the number of ways to assign Khem and Sem to different, non-adjacent cages.
Example 1
Example 2