问题文

dwango员工的Niwanngo君正在玩一个游戏。在这个游戏中，会出现Q个敌人，玩家需要巧妙操作来打败敌人。每个敌人都有一个称为“体力”的值，第i个敌人的体力是Ni。

Niwanngo君操作的玩家有一个称为“魔力”的固定值。当遇到敌人时，玩家的魔力为1。请注意，魔力每次遇到敌人都会重置为1。Niwanngo君可以在每个回合中执行以下操作之一：

• 操作1：增加魔力1。
• 操作2：将当前魔力记为x，将魔力更改为2x。
• 操作3：将当前魔力记为x，将魔力更改为2x+1。

当玩家的魔力恰好等于敌人的体力时，特殊的魔法会被触发，可以击败敌人。然而，如果魔力超过敌人的体力，则无法再击败敌人。因此，不要执行使魔力超过敌人体力的操作。玩家的操作不会改变敌人的体力。

Niwanngo君想知道击败敌人的操作方法有多少种。对于每个敌人，请计算Niwanngo君击败敌人的操作方法数，结果对1,000,000,007取模。请注意，如果中途执行的操作编号有所不同，则即使魔力的变化过程完全相同，也应将其视为不同的操作方法。

限制条件

• $1 \leq Q \leq 200$
• $1 \leq N_i \leq 10^{18}$ ($1 \leq i \leq Q$)
• $N_i$为整数

部分分

• 如果满足$Q = 1$且$1 \leq N_1 \leq 10^{14}$的测试数据集，可以获得$1300$分。

---

输入

输入以以下格式从标准输入中给出。

$Q$ $N_1$ $N_2$ $:$ $N_Q$

输出

输出结果应包含Q行。第i行输出Niwanngo君击败第i个敌人的操作方法数，结果对1,000,000,007取模。

---

输入示例 1

1
4

输出示例 1

5

第1个敌人的体力为4。有以下5种操作方法可以使魔力恰好为4：

• 操作1，操作1，操作1。
• 操作1，操作2。
• 操作2，操作1，操作1。
• 操作2，操作2。
• 操作3，操作1。

请注意，无论首先执行操作1还是操作2，魔力的变化方式都是相同的，但请记住将这两个操作视为不同的操作方法。

---

输入示例 2

2
2
1

输出示例 2

2
1

对于第1个敌人，有两种操作方法可以击败敌人。

对于第2个敌人，玩家的魔力与敌人的体力相等，因此无需执行任何操作。请注意，玩家的魔力在遇到第2个敌人时重置为1。

---

输入示例 3

3
1000
2000
3000

输出示例 3

415443858
630306535
766913460

请不要忘记使用模1,000,000,007进行输出。

---

输入示例 4

10
983102606006243867
653718290103598600
364611268624595444
114746989192634390
81304291426411017
931878752092058491
395809284336497545
633900034071891379
895817108011279740
92661392530626177

输出示例 4

893653300
150104699
232570112
922156483
361136690
103094234
245249617
912578727
399641917
820143308