#include<bits/stdc++.h>
#define ll long long
#define  mod 1000000000
using namespace std;
void solve();
ll k;
vector<ll> b, c;

vector<vector<ll>> multiply(vector<vector<ll>> A, vector<vector<ll>> B ){
	//logic to multiply matrix
	vector<vector<ll>> C(k+1, vector<ll>(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<ll>> pow(vector<vector<ll>> A, ll n){
	if(n == 1)
		return A;

	if(n&1)
		return multiply(A,pow(A, n-1 ));
	else
		return multiply(pow(A,n/2),pow(A, n/2));
}

ll compute(ll n){
	// step 1
	// base case
	if(n == 0)
		return 0;
	if(n <= k)
		return b[n];

	// initialise first part of vector i.e F1
	std::vector<ll> F1;
	for (int i = 1; i <= k; ++i)
	{
		F1[i] = b[i];
	}

	// step 2
	// transform matrix
	vector<vector<ll>> trans(k+1, vector<ll>(k+1));
	for (int i = 1; i <= k; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			if(i < k){
				if(i == j-1){
					trans[i][j] = 1;
				}
				else
					trans[i][j] = 0;
			}
			else
				trans[i][j] = c[k+1-j];
		}
	}

	// step 3
	trans = pow(trans , n-1);

	// step 4
	// matrix with a vector;
	ll res = 0;
	for (int i = 1; i <= k; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			res =  (res + (trans[i][j] * F1[j]) % mod) % mod;
		}
	}
	return res;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);

#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("error.txt", "w", stderr);
freopen("output.txt", "w", stdout);
#endif

int t=1;
/*is Single Test case?*/cin>>t;
while(t--)
{
	solve();
	cout<<"\n";
}

cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
return 0;
}
void solve()
{
	ll k; cin>>k;
	for (int i = 1; i <= k; ++i)
	{
		ll temp; cin>>temp;
		b.push_back(temp);
	}
	for (int i = 1; i <= k; ++i)
	{
		ll temp; cin>>temp;
		c.push_back(temp);
	}

	ll n; cin>>n;
	cout<<compute(n);
}