#include<fstream>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
long long v[9];
void prodmatrice(long long o[9],long long u[9],long long s[9])
{
    s[0]=(o[0]*u[0]+o[1]*u[3]+o[2]*u[6])%666013;
    s[1]=(o[0]*u[1]+o[1]*u[4]+o[2]*u[7])%666013;
    s[2]=(o[0]*u[2]+o[1]*u[5]+o[2]*u[8])%666013;
    s[3]=(o[3]*u[0]+o[4]*u[3]+o[5]*u[6])%666013;
    s[4]=(o[3]*u[1]+o[4]*u[4]+o[5]*u[7])%666013;
    s[5]=(o[3]*u[2]+o[4]*u[5]+o[5]*u[8])%666013;
    s[6]=(o[6]*u[0]+o[7]*u[3]+o[8]*u[6])%666013;
    s[7]=(o[6]*u[1]+o[7]*u[4]+o[8]*u[7])%666013;
    s[8]=(o[6]*u[2]+o[7]*u[5]+o[8]*u[8])%666013;
}
void putere(long long x, long long s[9])
{
    long long c[9],i,aux[9],j;
    for(i=0;i<=8;i++)
        c[i]=v[i];
    for(i=0;i<=8;i++)
        s[i]=0;
    s[0]=1;
    s[4]=1;
    s[8]=1;
    for(j=0;(1<<j)<=x;j++)
    {
        if((1<<j)&x)
        {
            prodmatrice(s,c,aux);
            for(i=0;i<=8;i++)
               s[i]=aux[i];
        }
        prodmatrice(c,c,aux);
        for(i=0;i<=8;i++)
           c[i]=aux[i];

    }
}
int main()
{
    long long n,s[9],m,x,y,z,a,b,c,i;
    f>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z>>a>>b>>c>>n;
        v[0]=0;v[1]=1;v[2]=0;
        v[3]=0;v[4]=0;v[5]=1;
        v[6]=c;v[7]=b;v[8]=a;
        putere(n-2,s);
        g<<(s[6]*x+s[7]*y+s[8]*z)%666013<<"\n";
    }
}