#include<fstream>
#define m 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
long long sol[3][3],mat[3][3],iep[3][3],maux[3][3],n,t;
void mult(long long m1[3][3],long long m2[3][3])
{
	long long i,j,k,q,r;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
		{	
			maux[i][j]=0;
			for(k=0;k<3;k++)  maux[i][j]=(maux[i][j]+(m1[i][k]*m2[k][j])%m)%m;
		}
		for(q=0;q<3;q++) for(r=0;r<3;r++) sol[q][r]=maux[q][r];
}
int main()
{
	long long q,r,i,j;
	f>>t;
	for(i=0;i<t;i++)
	{
		f>>iep[2][0]>>iep[1][0]>>iep[0][0]>>mat[0][0]>>mat[0][1]>>mat[0][2]>>n;
		mat[1][0]=mat[2][1]=1;
		n-=2;
		for(q=0;q<3;q++) for(r=0;r<3;r++) sol[q][r]=(q==r);
		for(j=31;j>=0;j--)
		{
			mult (sol,sol);
			if((1<<j)&n) mult (sol,mat);
		}
		mult (sol,iep);
		g<<sol[0][0]<<'\n';
	}
	return 0;
}