Rekursiv ardıcıllıq

a_i tam ədədlər ardıcıllığı növbəti şəkildə verilmişdir:

a_i = b_i (i ≤ k üçün)

a_i = c_1 a_{i-1} + c_2 a_{i-2} + ... + c_k a_{i-k} (i > k üçün)

burada b_j və c_j (1 ≤ j ≤ k) – verilmiş tam ədədlərdir. Verilmiş n üçün a_n hesablamaq və 10^9 modluna görə vermək tələb olunur.

Giriş verilənləri

Birinci sətir testlərin t sayını ehtiva edir. Hər bir test dörd sətir ehtiva edir:

k - (c) və (b) elementlərinin sayı (1 ≤ k ≤ 10);

b_1, ..., b_k (0 ≤ b_j ≤ 10^9) - boşluqla ayrılmış k tam ədəd;

c_1, ..., c_k (0 ≤ c_j ≤ 10^9) - k boşluqla ayrılmış k tam ədəd;

n – natural ədəd (1 ≤ n ≤ 10^9).

Çıxış verilənləri

Hər bir test üçün a_n qiymətlərini 10^9 modluna görə ehtiva edən t sətir verməli.

Nümunələr