Məsələlər
Rekursiv ardıcıllıq
Rekursiv ardıcıllıq
\textbf{a_i} tam ədədlər ardıcıllığı növbəti şəkildə verilmişdir:
\textbf{a_i} = \textbf{b_i} (\textbf{i} ≤ \textbf{k }üçün)
\textbf{a_i} = \textbf{c_1} \textbf{a_\{i-1\}} + \textbf{c_2 a_\{i-2\}} + ... + \textbf{c_k a_\{i-k\}} (\textbf{i} > \textbf{k }üçün)
burada \textbf{b_j} və \textbf{c_j} (\textbf{1} ≤ \textbf{j} ≤ \textbf{k}) -- verilmiş tam ədədlərdir. Verilmiş \textbf{n} üçün \textbf{a_n} hesablamaq və \textbf{10^9} modluna görə vermək tələb olunur.
\InputFile
Birinci sətir testlərin \textbf{t} sayını ehtiva edir. Hər bir test dörd sətir ehtiva edir:
\textbf{k} - (\textbf{c}) və (\textbf{b}) elementlərinin sayı (\textbf{1} ≤ \textbf{k} ≤ \textbf{10});
\textbf{b_1}, ..., \textbf{b_k} (\textbf{0} ≤ \textbf{b_j} ≤ \textbf{10^9}) - boşluqla ayrılmış \textbf{k} tam ədəd;
\textbf{c_1}, ..., \textbf{c_k} (\textbf{0} ≤ \textbf{c_j} ≤ \textbf{10^9}) - \textbf{k} boşluqla ayrılmış \textbf{k} tam ədəd;
\textbf{n} -- natural ədəd (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^9}).
\OutputFile
Hər bir test üçün \textbf{a_n} qiymətlərini \textbf{10^9} modluna görə ehtiva edən \textbf{t} sətir verməli.
Giriş verilənləri #1
3 3 5 8 2 32 54 6 2 3 1 2 3 4 5 6 6 3 24 354 6 56 57 465 98765432
Çıxış verilənləri #1
8 714 257599514