#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int X,Y,Z,A,B,C,N,M;
long long mat[5][5];

void inmultire(long long a[5][5],long long b[5][5], long long c[5][5])
{int i,j,k;

 for(i=1;i<=4;i++)
     for(j=1;j<=4;j++)
            for(k=1;k<=4;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%MOD;
}

void exponentiere(long long a[5][5],long long b[5][5], int p )
{
    if(p==1)
    {
        long long i,j,I,J;
        for(i=1; i<=4; i++)
            for(j=1; j<=4; j++)
                b[i][j]=a[i][j];
    }
    else if(p%2==0)
    {
        long long  i,j,I,J,c[5][5]= {0};
        exponentiere(a,b,p/2);
        inmultire(b,b,c);
        for(i=1 ; i<=4 ; i++)
            for(j=1 ; j<=4 ; j++)
                b[i][j] = c[i][j];
    }
    else
    {
        long long i,j,I,J,c[5][5]= {0};
        exponentiere(a,b,p-1);
        inmultire(a,b,c);
        for(i=1 ; i<=4 ; i++)
            for(j=1 ; j<=4 ; j++)
                b[i][j] = c[i][j];
    }
}

void nriepuri ()
{
    long long rez[5][5]= {0},a[5]= { 0, X, Y, Z, C*X+B*Y+A*Z},c[5] = {0};
    if (N==3)
    {
        fout<<a[4]<<"\n";
        return ;
    }
    exponentiere(mat,rez,N-3);
    for(int k=1 ; k<=4 ; k++)
        {
            for(int j=1 ; j<=4 ; j++)
                cout<<rez[k][j]<<" ";
            cout<<"\n";
        }
    int I,i,J,j;

    for(i=1; i<=4; i++)
        for(I = 1 ; I <=4 ; I++)
            {
                c[i]+=a[I]*rez[I][i];
            }
    fout<<c[4]<<"\n";
}

void read()
{
    fin>>M;
    for(int i=1 ; i<=M ; i++)
    {
        fin>>X>>Y>>Z>>A>>B>>C>>N;
        mat[2][1] = 1;
        mat[3][2] = 1;
        mat[4][3] = 1;
        mat[2][4] = C;
        mat[3][4] = B;
        mat[4][4] = A;

        nriepuri() ;
    }

}

int main()
{
    read();

    return 0;
}