//#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
#define vii vector <vector <long long> >
long long t,x,y,z,a,b,c,n,d[100];
vii prod(vii a,vii b){
    vii aux;
    for(long long i=0;i<a.size();i++){
        aux.push_back({});
        for(long long j=0;j<b.size();j++){
            aux[i].push_back(0);
        }
    }
    for(long long i=0;i<a.size();i++){
        for(long long j=0;j<b[i].size();j++){
            for(long long k=0;k<b.size();k++){
                aux[i][j]+=a[i][k]*b[k][j];
                aux[i][j]%=666013;
            }
        }
    }
    return aux;
}
vii lgput(vii a,long long k){
    if(k==1)
        return a;
    vii aux=lgput(a,k/2);
    if(k%2==0){
        aux=lgput(aux,k/2);
        aux=prod(aux,aux);
        return aux;
    }
    aux=lgput(aux,k/2);
    aux=prod(aux,aux);
    aux=prod(aux,a);
    return aux;
}
int main()
{
    cin>>t;
    while(t--){
        cin>>x>>y>>z>>a>>b>>c>>n;
        d[0]=x;
        d[1]=y;
        d[2]=z;
        vii mat;
        mat.push_back({a,1,0});
        mat.push_back({b,0,1});
        mat.push_back({c,0,0});
        vii auxx=lgput(mat,n-2);
        //cout<<auxx[0][0]<<" "<<auxx[1][0]<<" "<<auxx[2][0]<<"->";
        long long rasp=auxx[0][0]*z%666013+auxx[1][0]*y%666013+auxx[2][0]*x%666013;
        rasp%=666013;
        cout<<rasp<<"\n";
        //for(long long i=3;i<=n;i++){
            //d[i]=d[i-1]*a+d[i-2]*b+d[i-3]*c;
        //}
        //cout<<d[n]<<"\n";
    }
    return 0;
}