Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2625
Rearrange Them

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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.

Input:

Each test case just contains one integer, the number of people you have to rearrange.

Output:

The number of strategies you have to rearrange them, with the condition above.

Sample Input:

3
4

Sample Output:

3
11


Author: ZHOU, Kai
Source: ZOJ Monthly, November 2005
Submit    Status