Задачи
Рекурсивная последовательность
Рекурсивная последовательность
Последовательность a_i целых чисел задана следующим образом:
a_i = b_i (для i ≤ k) a_i = c_1a_{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 для каждого теста.
Пример
Входные данные #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
Выходные данные #1
8 714 257599514