Problem 1075 --Bob的高级组合数

1075: Bob的高级组合数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 67  Solved: 13
[Submit][Status][Web Board][Creator:]

Description

Alice和Bob是好朋友,他们都很喜欢数学,尤其是对组合数有着浓厚的兴趣。我们知道,普通的组合数公式为:

 

有一天,Bob和Alice在一起玩一个关于组合数的游戏,谁算不出来答案,就要请对方吃糖。但Alice觉得计算普通的组合数太简单了,于是她定义了一种高级组合数:

 

而Bob觉得这样还是太简单了,因此,他希望能够对于非负整数n,计算:

 

这可把Alice难住了,请你写个程序帮Alice算出正确答案。

由于数值过大,请把答案模100000007后输出。

Input

第一行一个整数T,表示询问次数。(T<=5000)
接下来T行,每行一个整数n。(0<=n<=1000000)

Output

对于每个整数n,在一行中输出所对应的答案

Sample Input

3
1
2
10

Sample Output

3
7
5842

HINT


表示n/2向下取整

Source

[Submit][Status]