测试数据来自 system/3024

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有若干球堆成一堆，堆放可以有多层，上层的球数量应少于下层的数量，每层的球排成一条直线，且紧挨在一起（中间不能留空）。下图是底层有 12 个球的一种堆放方式的剖面图：
　　　　　　
　　那么底层有 \(n\) 个球时，有多少种不同的堆放方式？

【输入格式】

　　第一行整数 \(T\)，表示数据组数，接下来的 \(T\) 行，每行一个整数 \(n\)，表示该组数据底层的球数量。

【输出格式】

　　包含 \(T\) 行，每行输出一个整数，表示对应输入的答案，这个数可能很大，你只需输出 \(mod\ 10007\) 的结果。

【输入输出样例】

　Input

4
1
2
3
5

　Output

1
2
5
34

【样例解释】

　　当 \(n=3\) 时，有下列 5 种堆放方式：

【数据限制】

　　对于 \(20\%\) 的数据，\(T≤10\)，\(n≤20\)。
　　对于 \(70\%\) 的数据，\(T≤3000\)，\(n≤5000\)。
　　对于 \(100\%\) 的数据，\(T≤100000\)，\(n≤2000000\)。

【来源】

　　Mr.he