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