Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 431
Solved: 110
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
Submit