#include <fstream>
#include <stdio.h>
using namespace std;
ifstream inte("iepuri.in");
ofstream oute("iepuri.out");
#define mod 666013
void multiply(long long a[3][3], long long b[3][3])
{	int i,j,k;
	long long c[3][3];
	memset(c,0,sizeof(c));
	for (i=0;i<3;i++)
		for(j=0;j<3;j++)
			for(k=0;k<3;k++)
				c[i][j]+=(a[i][k]*b[k][j]) % mod;
	for(i=0;i<3;i++)
		for(j=0;j<3;j++)
			b[i][j]=c[i][j] % mod;
}
int main()
{
	long long p[3][3];
	long long q[3][3];
	long long t,x,y,z,a,b,c,n,i,val;
	inte>>t;
	for (i=1;i<=t;i++)
	{
		inte>>x>>y>>z>>a>>b>>c>>n;
		memset(p,0,sizeof(p));
		memset(q,0,sizeof(q));
		q[0][0]=z;
		q[1][0]=y;
		q[2][0]=x;
		p[0][0]=a;
		p[0][1]=b;
		p[0][2]=c;
		p[1][0]=1;
		p[2][1]=1;
		n=n-2;
		val=n;
		for(val=n;val;val>>=1)
		{	if (val&1)
			{multiply(p,q);}
		multiply(p,p);}
			oute<<q[0][0]<<endl;
		}
	return 0;
}