...
#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;
}