No.658 テトラナッチ数列 Hard

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 95
作問者 : ミドリムシミドリムシ / テスター : cielciel
3 ProblemId : 1973 / 出題時の順位表

問題文

テトラナッチ数列というものがある。
テトラナッチ数列(ここでは{$T_n$})は次のように定義される。
・$T_1 = 0,$ $T_2 = 0,$ $T_3 = 0,$ $T_4 = 1$
・$T_k = T_{k-1}$ $+$ $T_{k-2}$ $+$ $T_{k-3}$ $+$ $T_{k-4}$

テトラナッチ数列の$n_i$番目の項$T_{n_i}$を17で割った余りを求めなさい。

入力

$Q$
$n_1$
$n_2$

:

$n_Q$

入力は$n+1$行与えられ、
1行目にはクエリの回数を表す整数$Q(1 \leq Q \leq 10^4)$、
$i+1(1 \leq i \leq Q)$行目には整数$n_i(1 \leq n_i \leq 10^{18})$
が与えられる。

出力

$Q$行出力し、
$i(1 \leq i \leq Q)$行目にはテトラナッチ数列の$n_i$番目の項$T_{n_i}$を17で割った余りを出力せよ。
末尾に改行を入れること。

サンプル

サンプル1
入力
2
3
10
出力
0
12

テトラナッチ数列の3番目の項は0、10番目の項は29なので、17で割った余りは12。

サンプル2
入力
6
3
2
1
3
1
4
出力
0
0
0
0
0
1

入力は全て違う値とは限らない。

サンプル3
入力
7
99
9999
999999
99999999
9999999999
999999999999
99999999999999
出力
12
16
14
13
6
16
9

入力は32bit整数値におさまらないことがある。

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

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