No.3036 Restricted Lucas (Easy)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 24
作問者 : cielciel

0 ProblemId : 2166 / 出題時の順位表

まえがき

本問は https://codeiq.jp/q/1603 の供養です(※こちらは公開されなかったため、本URLにはCodeIQのアカウントを持っていてもアクセス出来ません)

問題文

リュカ数列とは、
L(0)=2,L(1)=1,L(2)=3,L(3)=4,L(4)=7,...
のようなL(N+2)=L(N)+L(N+1)となる数列である。
このN項目を、1000000007で割った余りを求めよ。ただし以下の文字をソースコードに記述することは禁止される。

0 1 2 3 4 5 6 7 8 9 \ " ' * / %

専門的なこと (必要がなければ読む必要はありません、本問とは直接は関係しません)

https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%A5%E3%82%AB%E6%95%B0%E5%88%97 に記載のある、「Vn (1, -1)は(通常の)リュカ数である」が本問のリュカ数列と同義です。

入力

T
N1
N2
…
NT

T: ケース数
Ni (1<=i<=T): 求めるべきリュカ数列の項数

1 <= T <= 100
1 <= Ni <= 2000000000

出力

1行ごとに、リュカ数列のNi項目を1000000007で割った余りを出力せよ。

最後に改行してください。

サンプル

サンプル1
入力
3
10
43
2000000000
出力
123
969323029
2207

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。