1. 问题
如果世界杯观看台上有n个座位，游客们来到这里自由占位。普通情况下，一个游客首先考虑的座位肯定是两边都没人的座位。其次考虑的是一边没人的座位。最后没得考虑，仅仅能随便选一张两边都是人的座位。 如果有n个游客依次到场占位，每一个人都是依照上述规则选择自己的位子。求这n个游客占位的可能顺序有多少种？
输入描写叙述： 有多组測试数据。每组測试数据包含一个正整数n(0<n<1000000)。
输出描写叙述：对于每组数据。因为答案可能会非常大，所以输出：答案%1000000007
2. 分析
须要注意的是：观众来的顺序是固定的，场地是环形的。
分析：第一批（前几位）观众肯定选择两边没有人的位置，第二批（接下来）的观众肯定选择一边没有人的，第三批（最后）仅仅能选择两边都有人的座位。因此我们能够按批次安排这n个人。即先安排第一批。再安排第二批。最后安排第三批。
定义：当座位为{有人、无人、无人、有人}时。称这四个座位为TB模块。每一个TB模块间隔2个空座位。n为座位数。tb为TB模块个数。interval为间隔个数。
第一批：第一批观众入座之后需保证剩下的全部空座位至少一边有人。
第二批：安排仅仅有一边没有人的座位。易得这样座位的个数与TB模块个数m的两倍同样，则共同拥有2m*m!种顺序。
第三批：安排两边均有人的c个座位。
显然共同拥有c!种顺序。
我们依照TB模块的个数分情况讨论，则对于每种情况共同拥有：pi=(n*Cintervaltb*(interval-1)!)*(2tb*tb!)*((n-interval-tb)!)种情况顺序。当中(n*Cintervaltb*(interval-1)!)为第一批。(2tb*tb!)为第二批，((n-interval-tb)!)为第三批。对于第一批来说共同拥有interval个间隔，当中tb个TB模块。因此共同拥有Cintervaltb种座位间隔安排方式，第一个人已经选定位置，因此其它(interval-1)个人共同拥有(interval-1)。种顺序，因此第一批共同拥有n*Cintervaltb*(interval-1)!种顺序。对于第二批共同拥有tb个TB模块，则共同拥有2tb种安排顺序，tb个人共同拥有tb!个顺序。因此共同拥有2tb*tb!种顺序。
剩余的第三批共同拥有n-interval-tb个座位，因此共同拥有(n-interval-tb)!种顺序。
全部情况顺序数之和即为终于结果。易得当n为奇数时。tb最小值为1；反之，tb最小值为0。
例1：如果有8个座位，
(1) 情况一：不存在TB模块。第一个人共同拥有8种选择。当第一个人选定后，其他3个座位也固定下来（如：第一个人选择位置1，则另外三个座位肯定是3, 5, 7）。而接下来的这三个人能够有3！种顺序。
因此，可得第一批人第一种情况共8*C40*3！
种顺序。不存在TB模块即不存在第二批安排。
最后须要安排的第三批座位数为4，共同拥有4！种顺序。由上可得情况一共同拥有p1=8*3!*4!种顺序。
(2) 情况二：存在2个TB模块。
简单分析可得不存在一个TB模块的情况。
此时间隔数为(8-3*2)/2+2=3个。即一个间隔为1，2个间隔为2。当第一个人固定后。间隔共同拥有C32种分配方案，则该种情况共同拥有8*C32*2!种情况。易得安排第二批人共同拥有22*2。种顺序，第三批人共同拥有3！种顺序。则情况二共同拥有p2=(8*C32*2!)*(22*2!)*(3!)种顺序。
(3) 情况三：存在4个TB模块。
显然对于8不可能，因此第一批人分情况处理完毕。
综上，当座位数为8时共同拥有p1+p2种顺序。
注意：上述中每种情况均添加两个TB模块，直到达到TB模块的上界。则执行终止。
例2：如果有9个座位，
情况一：存在1个TB模块。间隔个数为(9-3*1)/2+1=4个，即3个间隔座位数为1，1个间隔座位数2。当第一个人选定后间隔共同拥有C41种分配方案。则该种共同拥有9*C41*3!种顺序。显然安排第二批人共同拥有21*1！
种情况，第三批人共同拥有4！种顺序。
则情况一共同拥有p3=(9*C41*3!)*(21*1！)*(4!)种顺序。
情况二：存在3个TB模块。
间隔个数为(9-3*3)/2+3=3个，即0个间隔座位为1。3个间隔座位数为2。
当第一个人选定后间隔共同拥有C33种分配方案，则第一批共同拥有9*C33*2!中顺序。易得，第二批人共同拥有23*3。种顺序。第三批人共同拥有3！
种顺序。
则情况二共同拥有p4=(9*C33*2!)*(23*3！)*(3!)种顺序。
情况三：显然不存在5个TB模块。
执行终止。
综上，当座位数为9时共同拥有p=p3+p4种顺序。
由例1与例2可得，当座位数为奇数与偶数时，情况不同。同样的是每种情况递增2个TB模块。
3. 实现
n为座位数。tb为TB模块个数。interval为间隔个数。num为全部观众的顺序。则对于每一种情况均有pi=(n*Cintervaltb*(interval-1)!)*(2tb*tb!)*((n-interval-tb)!)。
伪代码：
input: n
output: num
num = 0;
if n is odd
tb = 1;
else
tb = 0;
interval = (n-3*tb)/2 + tb;
while n ≥ 3*tb
p=(n*Cintervaltb*(interval-1)!)*(2tb*tb!)*((n-interval-tb)!);
num += p;
tb += 2;
interval--;
return num;
4. 遗留问题
当仅仅需保留余数时，阶乘的余数能够在每次相乘之前取余。即(a*b)%c =((a%c)*(b%c))%c。但Cmn%c怎样求解？坐等高人指点迷津……