1429: 摘麦穗

据说苏格拉底曾经要求弟子们在麦地里摘一颗最大的麦穗。

此处，我们认为麦穗的大小为$n$的排列，即由$n$个不同的整数组成的数组，这些整数从$1$到$n$按任意顺序排列。

例如,$[2,3,1,5,4]$是一个排列，但$[1,2,2]$不是一个排列($2$在数组中出现了两次)，$[1,3,4]$也不是一个排列($n=3$但数组中有$4$)。

弟子从起点走到终点只可进不可退，他们看不见后面麦穗的大小，不知道见到的麦穗的代表大小的数字，但他们能准确比较不同麦穗的大小。

我们认为得运者并不会只有一次摘取麦穗的机会。每当他手中的麦穗比见到的麦穗小，他就会摘掉那颗麦穗,并把手中的麦穗替换成见到的麦穗。

麦田的麦穗的排列完全随机，即每种排列出现的概率是完全相等的。

emaster想问你,得运者在麦田里摘取麦穗次数的期望是多少？

请输出期望对$10^9+7$取模的结果。

第一行，一个整数$t$,代表询问次数

接下来$t$行，每行一个整数$n$，代表麦穗大小的排列的大小。

数据范围:

$1 \le t \le 10^5$

$1 \le n \le 10^5$

4
1
2
3
100000

1
500000005
833333341
337069953

$n=1$时，出现的排列只可能是$[1]$,摘取次数只可能是$1$，对$10^9+7$取模后答案为1。

$n=2$时，排列$[1,2],[2,1]$等可能出现，摘取次数分别为$2，1$，摘取次数期望为$(2+1)/2$,对$10^9+7$取模后答案为$500000005$。

关于分数取模:

假定一个分数为$\frac{b}{a}$,其对$10^9+7$取模的结果就是对 $b*a^{-1}$ 取模$10^9+7$，其中 $a^{-1}$ 为 $a$ 的逆元。

例如$\frac{3}{2}$对$10^9+7$取模。$2$ 关于$10^9+7$的逆元为 $500000004$ ，$3*500000004$取模$10^9+7$的结果为$500000005$，即所求答案。

此外$\frac{b}{a}*\frac{d}{c}$对$10^9+7$取模即$b*d*a^{-1}*c^{-1}$对$10^9+7$取模。

如果你不会求 $a$ 关于$10^9+7$的逆元。以下给出一个当模数为质数时适用的模板。

```c++

long long inv(long long a)

{

long long MOD=1e9+7,b=MOD-2;

a%=MOD;

long long res=1;

while(b>0)

{

if(b&1) res=(res*a)%MOD;

a=(a*a)%MOD;

b>>=1;

}

return res;

}

```

调用inv(a)的返回结果即为 $a$ 关于 $10^9+7$ 的逆元。