Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
124 - ZOJ Monthly, March 2013 - C
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 ?

Input

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.

Output

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

Sample Input

2
4

Sample Output

0
2

Hint

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
Submit    Status