AT_dwacon2018_final_d ニワンゴくんとゲーム

[problemUrl]: https://atcoder.jp/contests/dwacon2018-final/tasks/dwacon2018_final_d dwango社員のニワンゴくんは、あるゲームで遊んでいます。 このゲームでは、$ Q $ 体の敵が現れるので、プレイヤーをうまく操作して敵を倒す必要があります。 また、敵にはそれぞれ **体力** と呼ばれる値が定まっており、$ i $ 番目の敵の体力は $ N_i $ です。 ニワンゴくんの操作するプレイヤーには、**魔力** とよばれる値が定まっています。 敵と遭遇したとき、プレイヤーの魔力は $ 1 $ です。 この魔力は、敵と遭遇するたびに $ 1 $ に戻ることに注意してください。 ニワンゴくんは、毎ターン、次の操作のうちいずれかを行うことができます。 - 操作 $ 1 $: 魔力を $ 1 $ 増加させる。 - 操作 $ 2 $: 現在の魔力を $ x $ として、魔力を $ 2x $ に変更する。 - 操作 $ 3 $: 現在の魔力を $ x $ として、魔力を $ 2x\ +\ 1 $ に変更する。 プレイヤーの魔力がちょうど敵の体力に等しくなったとき、特殊な魔法が発動し、敵を倒すことができます。 ただし、魔力が敵の体力を超えてしまうと、もう敵を倒すことはできません。そのため、魔力が敵の体力を超えてしまうような操作を行ってはいけません。 プレイヤーの操作によって敵の体力が変化することはありません。 ニワンゴくんは、敵を倒すまでの操作の方法は何通りあるかが気になっています。 それぞれの敵に対して、ニワンゴくんが敵を倒すまでの操作の方法は何通りあるかを $ {\rm\ mod}\ 1,000,000,007 $ で求めてください。 ここで、途中で行う操作の番号が一回でも異なれば、途中の魔力の経過がまったく同じでも、異なる操作の方法として数えることに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ N_1 $ $ N_2 $ $ : $ $ N_Q $

答えを $ Q $ 行で出力せよ。$ i $ 行目には、$ i $ 番目の敵を倒すまでの操作の方法は何通りあるかを $ {\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 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ 番目の敵の体力は $ 4 $ です。 魔力をちょうど $ 4 $ にするまでの操作の方法としては、次の $ 5 $ 通りがあります。 - 操作 $ 1 $, 操作 $ 1 $, 操作 $ 1 $ の順に操作を行う。 - 操作 $ 1 $, 操作 $ 2 $ の順に操作を行う。 - 操作 $ 2 $, 操作 $ 1 $, 操作 $ 1 $ の順に操作を行う。 - 操作 $ 2 $, 操作 $ 2 $ の順に操作を行う。 - 操作 $ 3 $, 操作 $ 1 $ の順に操作を行う。 ここで、最初に操作 $ 1 $ を行っても、操作 $ 2 $ を行っても、魔力の変化の仕方は変わりませんが、この $ 2 $ つの操作は区別することに注意してください。 ### Sample Explanation 2 $ 1 $ 番目の敵については、この敵を倒すまでの操作の方法は $ 2 $ 通りあります。 $ 2 $ 番目の敵については、一切操作を行わなくても最初からプレイヤーの魔力が敵の体力と等しくなっています。 ここで、プレイヤーの魔力は $ 2 $ 番目の敵と遭遇した際に $ 1 $ に戻ることに注意してください。 ### Sample Explanation 3 $ {\rm\ mod}\ 1,000,000,007 $ で出力するのを忘れないようにしてください。