#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MOD 1000000000
using namespace std;
ll k;
vectora, b, c;
vector<vector> multiply(vector<vector>A, vector<vector>B)
{
//logic to multiply matrix
vector < vector>C(k + 1, vector(k + 1));
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= k; j++)
{
for (int x = 1; x <= k; x++)
{
C[i][j] = (C[i][j] + (A[i][x] * B[x][j]) % MOD) % MOD;
}
}
}
return C;
}
vector<vector> pow(vector<vector>A, ll p)
{
if (p == 1)
{
return A;
}
//POWER IS ODD
if (p & 1)
{
return multiply(A, pow(A, p - 1));
}
vector < vector<ll>>X = pow(A, p / 2);
return multiply(X, X);
}
ll compute(ll n)
{
/base case/if (n == 0) return 0;
/base case/if (n <= k) return b[n - 1];
//indexing
std::vector F1(k + 1);
for (int i = 1; i <= k; i++)
{
F1[i] = b[i - 1];
}
// tranformation matrix
vector < vector> T(k + 1, vector(k + 1));
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= k; j++)
{
if (i < k)
{
if (j == (i + 1))
{
T[i][j] = 1;
}
else
{
T[i][j] == 0;
}
}
else
{
T[i][j] = c[k - j];
}
}
}
T = pow(T, n - 1);
//STEP 4
ll res = 0;
for (int i = 1; i <= k; i++)
{
res = (res + (T[1][i] * F1[i])) % MOD;
}
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(“cbinput.txt”, “r”, stdin);
freopen(“cboutput.txt”, “w”, stdout);
#endif
ll t, n, num;
cin >> t;
while (t–)
{
//vector f1
cin >> k;
for (int i = 0; i < k; i++)
{
cin >> num;
b.pb(num);
}
//coefficients
for (int i = 0; i < k; i++)
{
cin >> num;
c.pb(num);
}
//nth value
cin >> n;
cout << compute(n) << endl;
b.clear();
c.clear();
}
return 0;
}