Последовательность a_i целых чисел задана следующим образом:
a_i = b_i (для i ≤ k) a_i = c_1 a_{i-1} + c_2 a_{i-2} + ... + c_k a_{i-k} (для i > k)
где b_j и c_j (1 ≤ j ≤ k) - заданные целые числа. Для заданного n следует вычислить a_n и вывести его по модулю 10^9.
Первая строка содержит количество тестов t. Каждый тест состоит из четырех строк:
k - количество элементов (c) и (b) (1 ≤ k ≤ 10);
b_1, ..., b_k (0 ≤ b_j ≤ 10^9) - k целых чисел, разделенных пробелом;
c_1, ..., c_k (0 ≤ c_j ≤ 10^9) - k целых чисел, разделенных пробелом;
n - натуральное число (1 ≤ n ≤ 10^9).
В точности t строк, каждая из которых содержит значение a_n по модулю 10^9 для каждого теста.