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

#define DIM 3
#define MOD 666013

int z[4][4],sol[4][4],a,b,c;

inline void init(int x[4][4])
{
	int i,j;
	for(i=1;i<=3;i++)
		for(j=1;j<=3;j++) {
			sol[i][j]=0;
			x[i][j]=0;
		}
	x[2][1]=1;
	x[3][2]=1;
	x[1][3]=c;
	x[2][3]=b;
	x[3][3]=a;
	sol[1][1]=1;
	sol[2][2]=1;
	sol[3][3]=1;
}

inline void mult(int x[4][4], int y[4][4])
{
	int i,j,k;
	for(i=1;i<=DIM;i++)
		for(j=1;j<=DIM;j++) {
			z[i][j]=0;
			for(k=1;k<=DIM;k++)
				z[i][j]=(z[i][j]+(1LL*x[i][k]*y[k][j])%MOD)%MOD;
		}
	for(i=1;i<=DIM;i++)
		for(j=1;j<=DIM;j++)
			x[i][j]=z[i][j];
}

inline void putere(int n)
{
	int i,x[4][4];
	init(x);
    for(i=0;(1LL<<i)<=n;i++) {
        if(n&(1<<i))
			mult(sol,x);
		mult(x,x);
	}
}

int main ()
{
	int i,t,x,y,z,n,aux;
	ifstream f("iepuri.in");
	ofstream g("iepuri.out");
	f>>t;
	for(i=1;i<=t;i++) {
		f>>x>>y>>z>>a>>b>>c>>n;
		aux=x;
		x=y;
		y=z;
		z=a*y+b*x+c*aux;
		putere(n-1);
		g<<((1LL*x*sol[1][1])%MOD+(1LL*y*sol[2][1])%MOD+(1LL*z*sol[3][1])%MOD)%MOD<<'\n';
	}
	f.close();
	g.close();
	return 0;
}