#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 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);
        for(i=1 ; i<=4 ; i++)
            for(j=1 ; j<=4 ; j++)
                for(I=1 ; I<=4 ; I++ )
                {
                    c[i][j] +=b[i][I]*b[I][j];
                    c[i][j] = c[i][j]%MOD;
                }
        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);
        for(i=1 ; i<=4 ; i++)
            for(j=1 ; j<=4 ; j++)
                for(I=1 ; I<=4 ; I++ )
                {
                    c[i][j] += b[i][I]*a[I][j];
                    c[i][j] = c[i][j]%MOD;
                }
        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);

    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;
}