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

---

【题目描述】

　　大兴安岭每天都要生产大量的木材。这些木材在装上火车之前，伐木工会把它们成堆地放在车站旁的露天场地上，从侧面看这些木材堆的剖面图如下：
　　　　　　
　　我们知道，木材堆放可以有多层，上层的圆木数量应少于下层的数量，每层的圆木排成一条直线，且紧挨在一起（中间不能留空）。上图是底层有 12 根圆木堆的一种堆放方式。
　　现在给出在木材堆的最底层的木材数量 \(n\)，请你计算底层有 \(n\) 根木材堆有多少种不同的堆放方式。

【输入格式】

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

【输出格式】

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

【输入输出样例】

　Input

4
1
2
3
5

　Output

1
2
5
34

【样例解释】

【数据限制】

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

【来源】

　　Mr.he