#include <bits/stdc++.h>

using namespace std;

ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");

const int mod=666013;

int t,n;

void multmat(int q[][3],int qq[][3],int qqq[][3]){
    for(int i=0;i<=2;++i)
        for(int j=0;j<=2;++j)
            for(int k=0;k<=2;++k)
                qqq[i][j]=(qqq[i][j]+1LL*q[i][k]*qq[k][j])%mod;
}

void expmat(int q[][3],int qq[][3], long long qqq){
    int aux[3][3];
    for(long long int i=0;(1<<i)<=qqq;++i){
        if(qqq&(1<<i)){
            memset(aux,0,sizeof aux);
            multmat(q,qq,aux);
            memcpy(q,aux,sizeof aux);
        }
        memset(aux,0,sizeof aux);
        multmat(qq,qq,aux);
        memcpy(qq,aux,sizeof aux);
    }
}

int main()
{
    int mat[3][3],st[3][3];
    fin>>t;
    while(t--){
        memset(mat,0,sizeof mat);
        memset(st,0,sizeof st);
        fin>>st[0][0]>>st[0][1]>>st[0][2]>>mat[2][2]>>mat[1][2]>>mat[0][2]>>n;
        mat[1][0]=mat[2][1]=1;
        expmat(st,mat,n-2);
        fout<<st[0][2]<<'\n';
    }
    return 0;
}