...

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9;
#define ll long long
#define mx 15
#define lp(i,a) 		for(ll i=0; i<a;i++)
#define Mat(mat,N,M)		lp(i,N){lp(j,M)cout<<mat[i][j]<<" \n"[j==M-1];}
ll T[mx][mx],I[mx][mx],a[mx],b[mx];
ll n,x;
void matmul(ll a[mx][mx],ll b[mx][mx],int dim)
{
	ll res[dim+1][dim+1];
	for(int i=0;i<dim;++i)
	{
		for(int j=0;j<dim;++j)
		{
			res[i][j]=0;
			for(int k=0;k<dim;++k)
			{
				res[i][j]=(res[i][j]+(a[i][k]*b[k][j])%mod)%mod;
			}
		}
	}
	for(int i=0;i<dim;++i)
	{
		for(int j=0;j<dim;++j)
		{
			a[i][j]=res[i][j];
		}
	}
}
 
void nthrec(ll x)
{
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			I[i][j]=0;
			if(i==j)I[i][j]=1;
			else I[i][j]=0;
		}
	}
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
		{
			T[i][j]=0;
			if(i<n-1)
			{
				T[i][i+1]=1;
			}
			else
			{
				T[i][j]=b[n-1-j];
			}
		}
	}
	while(x)
	{
		if(x&1ll)matmul(I,T,n);
		matmul(T,T,n);
		x>>=1ll;
	}
	cout<<I[n-1][n-1]<<endl;
	//Mat(I,n,n);
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;cin>>t;
    while(t--)
    {
    	cin>>n;
    	for(int i=0;i<n;++i)cin>>a[i];
    	for(int i=0;i<n;++i)cin>>b[i];
    	cin>>x;
    	if(x<n)cout<<a[x-1]<<endl;
    	else nthrec(x);
	}
	return 0;
}