#include <fstream>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
#define NMAX 5005
#define MOD 666013

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

typedef int mat[3][3];
mat m;

void mult(mat a, mat b, mat aux) {
	int i,j,k;
	for(i=0;i<3;++i) {
		for(j=0;j<3;++j) {
			aux[i][j]=0;
			for(k=0;k<3;++k) aux[i][j]=(1LL*aux[i][j]+1LL*a[i][k]*b[k][j])%MOD;
		}
	}
}

void egal(mat a, mat b) {
	for(int i=0;i<3;++i)
		for(int j=0;j<3;++j) a[i][j]=b[i][j];
}

void pow(int p, mat &b) {
	mat a,x,aux;
	egal(a,b);
	for(int i=0;i<3;++i)
			for(int j=0;j<3;++j) x[i][j]=0;
	x[0][0]=x[1][1]=x[2][2]=1;

	for(int i=0;(1<<i)<=p;++i) {
		if(p&(1<<i)) {
			mult(x,a,aux);
			egal(x,aux);
		}

		mult(a,a,aux);
		egal(a,aux);
	}

	egal(b,x);
}

int main() {
	int t,a,b,c,p;

	fin>>t;
	while(t--) {
		for(int i=0;i<3;++i)
			for(int j=0;j<3;++j) m[i][j]=0;
		fin>>c>>b>>a>>m[0][0]>>m[0][1]>>m[0][2]>>p;
		m[1][0]=m[2][1]=1;

		pow(p-2, m);
		fout<<(1LL*m[0][0]*a+1LL*m[0][1]*b+1LL*m[0][2]*c)%MOD<<'\n';
	}

	return 0;
}