#include <cstdio>
#include<iostream>
using namespace std;

struct MATRIX
{
    long long v[4][4];

    MATRIX operator * (MATRIX b)
    {
        int i,j;
        MATRIX c;
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
        {
            c.v[j][i]=(this->v[1][i]*b.v[j][1] + this->v[2][i]*b.v[j][2] + this->v[3][i]*b.v[j][3])%666013;
        }
        return c;
    }

} x,y;



MATRIX multiply(int k);

int main()
{
    FILE *in,*out;
    in=fopen("iepuri.in","r");
    out=fopen("iepuri.out","w");
    long long n,i,k,init[4],j;
    fscanf(in,"%d",&n);
    //debugging
    /*for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            cin>>x.v[i][j];
    x=multiply(3);
    for(i=1;i<=3;i++)
    {
        for(j=1;j<=3;j++)
            cout<<x.v[i][j]<<" ";
        cout<<endl;
    }*/


    for(i=1;i<=n;i++)
    {
        fscanf(in,"%lld %lld %lld",&init[1],&init[2],&init[3]);
        fscanf(in,"%lld %lld %lld %d",&x.v[3][3],&x.v[2][3],&x.v[1][3],&k);
        x.v[1][1]=x.v[1][2]=x.v[2][2]=x.v[3][1]=0;
        x.v[2][1]=x.v[3][2]=1;
        y=multiply(k-2);
        fprintf(out,"%d\n",(y.v[1][3]*init[1]+y.v[2][3]*init[2]+y.v[3][3]*init[3])%666013);
    }
    return 0;
}

MATRIX multiply(int k)
{
    if(k==1) return x;
    if(k%2==0)
    {
        MATRIX i;
        i=multiply(k/2);
        return i*i;
    }
    if(k%2==1)
    {
        MATRIX i;
        i=multiply(k/2);
        i=i*i;
        i=x*i;
        return i;
    }

}