亿万富翁 Robin McBobin 和 Ronald Dump 正在玩一个“机会游戏”。

游戏共进行 $n$ 回合。每一回合，其中一名玩家拥有选择权，Robin 在第一回合拥有选择权。每一回合，屏幕上会出现一个从 $1$ 到 $m$ 之间均匀且独立随机选择的整数。拥有选择权的玩家必须决定：是接受这个数字并将选择权交给对手，还是将这个数字交给对手并保留自己的选择权。

Robin 和 Ronald 都更看重压制对手而非获得分数，因此双方都会选择能使自己与对手得分之差的期望值最大化的策略。双方均采取最优策略。

设 $d_n$ 为 $n$ 回合后 Robin 的得分总和与 Ronald 的得分总和之差的期望值。可以证明，对于 $m \ge 3$，存在一个有理数 $d$ 使得 $\lim_{n \to \infty} d_n = d$。你需要求出这个数。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 5 \cdot 10^5$)。

每个测试用例占一行，包含一个整数 $m$ ($3 \le m \le 10^9$)。

输出格式

对于每个测试用例，若 $d = \frac{P}{Q}$ 且 $P$ 与 $Q$ 互质，输出 $(P \cdot Q^{-1}) \pmod{10^9 + 7}$。保证 $Q \not\equiv 0 \pmod{10^9 + 7}$。

样例

样例输入 1

2
3
4

样例输出 1

1
333333337

说明

对于 $m = 3$，答案为 $d = 1$。对于 $m = 4$，答案为 $d = 1.333... = \frac{4}{3}$。