Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3688
The Review Plan II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Michael is very grateful for your last help of his review plan. Now he finds that it's interesting to do the review in a different way than ordinary students, he wants you to help him again.

The whole book he needs to review has N chapters, he wants to arrange exactly N days to take his review, and one chapter by each day.

But he does not want to read the ith(1 ≤ iN-1) chapter in the ith day or the (i+1)th day. And read the Nth chapter in the Nth day or in the first day is not acceptable too. Can you tell him how many different appropriate plans he could make ?


There are multiple test cases. For each test case there is a single line contains one integer N(1 ≤ N ≤ 100000), N is the number of the days and also the number of the chapters in the book.

Process to the end of input.


One line for each case. The number of the different appropriate plans module 1000000007.

Sample Input


Sample Output



For case 1, there is no such plan. For case 2, you can arrange the plan as (2, 3, 4, 1) or (3, 4, 1, 2).

Author: LI, Huang
Contest: ZOJ Monthly, March 2013
Submit    Status