#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <strings.h>
#define MOD 666013
using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
void I3(int x[3][3])
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(i==j) x[i][j]=1;
                else
                    x[i][j]=0;
}

void Mat0(int x[3][3])
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
                    x[i][j]=0;
}
void CopyMat(int p[3][3], int aux[3][3])
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            p[i][j]=aux[i][j];
}

void PutereLogaritmic(int x[3][3], int n, int p[3][3])
{
	I3(p);
	int aux[3][3]={0};
	while (n > 0)
	{
		if (n%2==1)
		{
		    Mat0(aux);
		    //p*=x;
			for(int i=0; i<3; i++)
                for(int j=0; j<3; j++)
                    for(int k=0; k<3; k++)
            {
                aux[i][j]+=p[i][k]*x[k][j]%MOD;
            }
			n-- ;
		CopyMat(p, aux);
		}
		Mat0(aux);
		for(int i=0; i<3; i++)
                for(int j=0; j<3; j++)
                    for(int k=0; k<3; k++)
            {
                aux[i][j]+=x[i][k]*x[k][j]%MOD;
            }
        CopyMat(x, aux);
		n/=2;
	}
}
void f(int p[3][3], int m[3][1])
{
    int aux[3][1]={0};
    int j=0;
            for(int i=0; i<3; i++)
                    for(int k=0; k<3; k++)
            {
                aux[i][j]+=p[i][k]*m[k][j]%MOD;
            }
    m[0][0]=aux[0][0];
    m[1][0]=aux[1][0];
    m[2][0]=aux[2][0];
}

void incarcareX(int x[3][3], int a, int b, int c)
{
    x[0][0]=a;
    x[0][1]=b;
    x[0][2]=c;
    x[1][0]=1;
    x[1][1]=0;
    x[1][2]=0;
    x[2][0]=0;
    x[2][1]=1;
    x[2][2]=0;
}

void incarcareM(int m[3][1], int x, int y, int z)
{
    m[0][0]=z;
    m[1][0]=y;
    m[2][0]=x;
}

void prelucrare(int x, int y, int z, int a, int b, int c, int n)
{
    int X[3][3];
    incarcareX(X, a, b, c);
    int p[3][3];
    PutereLogaritmic(X, n-2, p);
    int m[3][1];
    incarcareM(m, x, y, z);
    f(p, m);
    fout<<m[0][0]%MOD<<'\n';

}

int main()
{
    int T, x, y, z, a, b, c, n;
    fin>>T;
    for(int i=1;i<=T;i++)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        prelucrare(x, y, z, a, b, c, n);
    }
    return 0;
}