Sequence \textbf{a_i} of integer numbers is defined as follows: \textbf{a_i} = \textbf{b_i} (for \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\}} (for \textbf{i} > \textbf{k}) where \textbf{b_j} and \textbf{c_j} (\textbf{1} ≤ \textbf{j} ≤ \textbf{k}) are given integer numbers. Your task is to compute \textbf{a_n} for given \textbf{n} and output it modulo \textbf{10^9}. \InputFile On the first row there is the number \textbf{t} of test cases. Each test contains four lines: \textbf{k} - number of elements of (\textbf{c}) and (\textbf{b}) (\textbf{1} ≤ \textbf{k} ≤ \textbf{10}); \textbf{b_1},...,\textbf{b_k} (\textbf{0} ≤ \textbf{b_j} ≤ \textbf{10^9}) - \textbf{k} integers separated by spaces; \textbf{c_1}, ..., \textbf{c_k} (\textbf{0} ≤ \textbf{c_j} ≤ \textbf{10^9}) - \textbf{k} integers separated by spaces; \textbf{n} - natural number (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^9}). \OutputFile Exactly \textbf{t} lines, one for each test case: \textbf{a_n} modulo \textbf{10^9}.