問題文

dwango社員のニワンゴくんは、あるゲームで遊んでいます。 このゲームでは、$Q$ 体の敵が現れるので、プレイヤーをうまく操作して敵を倒す必要があります。 また、敵にはそれぞれ 体力 と呼ばれる値が定まっており、$i$ 番目の敵の体力は $N_i$ です。

ニワンゴくんの操作するプレイヤーには、魔力 とよばれる値が定まっています。 敵と遭遇したとき、プレイヤーの魔力は $1$ です。 この魔力は、敵と遭遇するたびに $1$ に戻ることに注意してください。 ニワンゴくんは、毎ターン、次の操作のうちいずれかを行うことができます。

• 操作 $1$: 魔力を $1$ 増加させる。
• 操作 $2$: 現在の魔力を $x$ として、魔力を $2x$ に変更する。
• 操作 $3$: 現在の魔力を $x$ として、魔力を $2x + 1$ に変更する。

プレイヤーの魔力がちょうど敵の体力に等しくなったとき、特殊な魔法が発動し、敵を倒すことができます。 ただし、魔力が敵の体力を超えてしまうと、もう敵を倒すことはできません。そのため、魔力が敵の体力を超えてしまうような操作を行ってはいけません。 プレイヤーの操作によって敵の体力が変化することはありません。

ニワンゴくんは、敵を倒すまでの操作の方法は何通りあるかが気になっています。 それぞれの敵に対して、ニワンゴくんが敵を倒すまでの操作の方法は何通りあるかを ${\\rm mod} 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$ 行目には、$i$ 番目の敵を倒すまでの操作の方法は何通りあるかを ${\\rm mod} 1,000,000,007$ で出力せよ。

---

入力例 1

1
4

出力例 1

5

$1$ 番目の敵の体力は $4$ です。 魔力をちょうど $4$ にするまでの操作の方法としては、次の $5$ 通りがあります。

• 操作 $1$, 操作 $1$, 操作 $1$ の順に操作を行う。
• 操作 $1$, 操作 $2$ の順に操作を行う。
• 操作 $2$, 操作 $1$, 操作 $1$ の順に操作を行う。
• 操作 $2$, 操作 $2$ の順に操作を行う。
• 操作 $3$, 操作 $1$ の順に操作を行う。

ここで、最初に操作 $1$ を行っても、操作 $2$ を行っても、魔力の変化の仕方は変わりませんが、この $2$ つの操作は区別することに注意してください。

---

入力例 2

2
2
1

出力例 2

2
1

$1$ 番目の敵については、この敵を倒すまでの操作の方法は $2$ 通りあります。

$2$ 番目の敵については、一切操作を行わなくても最初からプレイヤーの魔力が敵の体力と等しくなっています。 ここで、プレイヤーの魔力は $2$ 番目の敵と遭遇した際に $1$ に戻ることに注意してください。

---

入力例 3

3
1000
2000
3000

出力例 3

415443858
630306535
766913460

${\\rm mod} 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