eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Рекурсивная последовательность

Рекурсивная последовательность

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Последовательность a_i целых чисел задана следующим образом:

a_i = b_i (для ik) a_i = c_1a_{i-1} + c_2 a_{i-2} + ... + c_k a_{i-k} (для i > k)

где b_j и c_j (1jk) - заданные целые числа. Для заданного n следует вычислить a_n и вывести его по модулю 10^9.

Входные данные

Первая строка содержит количество тестов t. Каждый тест состоит из четырех строк:

k - количество элементов (c) и (b) (1k10);

b_1, ..., b_k (0b_j10^9) - k целых чисел, разделенных пробелом;

c_1, ..., c_k (0c_j10^9) - k целых чисел, разделенных пробелом;

n - натуральное число (1n10^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