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