
ZOJ Problem Set  3688
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 i^{th}(1 ≤ i ≤ N1) chapter in the i^{th} day or the (i+1)^{th} day. And read the N^{th} chapter in the N^{th} day or in the first day is not acceptable too. Can you tell him how many different appropriate plans he could make ? InputThere 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. OutputOne line for each case. The number of the different appropriate plans module 1000000007. Sample Input2 4 Sample Output0 2 HintFor 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 