1619 - 小明的细胞

Time Limit: 1s Memory Limit: 128MB

Submissions: 429 Solved: 109
Description

小明是一个喜欢思考的少年,他喜欢科学,有一天他做实验发现有一种奇怪的细胞,这种细胞新生以后第一分钟分裂产生一个新细胞,第二分钟产生两个新细胞,第三分钟产生3个新细胞,以此类推,到第五分钟分裂出5个新细胞,然后他就死亡了。小明想知道如果一开始有一个新生细胞,那么第N分钟到底有多少细胞。

Input

总共有T(T<=1000)组测试数据 在第一行中给出 接下来有T个模块 个模块开始个整数N(1<=N<=1000)表示时间N。

Output

输出结果共有T行,每行输出一个数表示第N分钟有多少个细胞。这个数可能很大,所以我们只关心结果对10007取余以后的值。

Sample Input
3
1
2
5
Sample Output
2
5
88
Hint
Source