该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

染染船长终于获得了宝藏！

宝藏是很多很多的金币（可以看成无穷多），染染需要与手下的 $n$ 名水手们分享金币。

根据大嘤帝国的传统，分配宝藏对于船长而言是一件稍不留神就会丧命的苦差事。这是由于，船长需要将每人能分到多少宝藏的决议公布，之后全体船员（包括船长）开会投票决定决议是否通过。如果半数及以上船员（包括船长）投票通过，船长就能够安全的执行决议；否则，船长就会被投海杀死，由第 1 顺位继承人继承船长的职位并再次分配，再不通过就继续投海杀死并由第 2 顺位继承人继承，依此类推。

好在经过多日的相处，染染知道手下的水手各个都是聪明绝顶又贪婪并且相互之间了如指掌的狠人！每个水手都会在保证自己不被杀死的前提下企图获得更大的利益。

现在，染染想要知道，如何分配给第 1, 2, ⋯, n 顺位继承人的金币数量，才能保证自己只需要分出去最少的金币就能保住自己的性命。

输出描述

本题单个测试点内包含多组测试数据。

• 输入第一行一个正整数 $T$ ($1 \leq T \leq 20$)，表示数据组数。
• 每组数据第一行一个正整数 $n$ ($1 \leq n \leq 10^9$)，表示染染手下不包括他自己在内的水手数量。

输出描述

为了避免输出量过大，输出对每组数据进行压缩。

对于每组数据，假设染染分配给船长的第 $i$ 顺位继承人的金币数量为 $r_i$，你只需要输出一行一个压缩后的非负整数 $R$： $R =( \sum_{i=1}^{n} i \cdot r_i) \mod (10^9 + 7)$

可以证明序列 $r_1, r_2, \cdots, r_n$ 唯一。

样例

2
1
2

0
2