問題文

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 点が与えられる。

入力例 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