ZOJ Problem Set - 2625
N people stand in a line, and we numbered them 1,2...n, and now you are asked to rearrange them. The ith people is considred in the front of the (i+1)th, after the rearrange, everyone the people in front of whom can not be the same one as before. How many different strategies you can do the rearrange.
Each test case just contains one integer, the number of people you have to rearrange.
The number of strategies you have to rearrange them, with the condition above.
Author: ZHOU, Kai
Source: ZOJ Monthly, November 2005