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

Послідовність 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 для кожного теста.

Приклади