题目描述

\(n\) 个数组成的一个序列\(\{An\}\)，如果满足 \(A_1<A_2<…<A_i>A_{i+1}>…>A_n\) \((1≤i≤n)\)，则称它为单峰序列。读入正整数 \(n\)，求 \(1，2，…，n\) 组成的全排列中，单峰序列的个数。例如：当 \(n=3\) 时，单峰序列有 \(123，132，231，321\) 四个。由于结果比较大，输出结果对 \(10007\) 的余数即可。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；接下来 \(t\) 行，每行一个正整数 \(n（2≤n≤2×10^9）\)

输出格式

对于每个正整数 \(n\)，输出相应结果对 \(10007\) 的余数。

样例1

输入样例1

2
3
100000

输出样例1

4
5238

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("single.in","r",stdin);
freopen("single.out","w",stdout);