#include <fstream>
using namespace std;

int a[4][4],aux[4][4],r[4][4];

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

void pow(int c[4][4],int a[4][4],int b[4][4])
{
	for (int i=1;i<4;i++)
		for (int j=1;j<4;j++)
		{
			c[i][j]=0;
			for (int k=1;k<4;k++,c[i][j]%=666013)
				c[i][j]+=a[i][k]*b[k][j];
		}
}

void copy(int a[][4],int b[][4])
{
	for (int i=1;i<4;i++)
		for (int j=1;j<4;j++)
			a[i][j]=b[i][j];
}

int main()
{
	int t,n;
	in>>t;
	while (t--)
	{
		in>>a[3][1]>>a[2][1]>>a[1][1]>>r[1][1]>>r[1][2]>>r[1][3]>>n;
		r[2][1]=r[3][2]=1;
		r[2][2]=r[2][3]=r[3][1]=r[3][3]=0;
		a[1][2]=a[2][2]=a[2][3]=a[1][3]=a[3][2]=a[3][3]=0;
		n-=2;
		for (;n;n>>=1)
		{
			if (n&1)
			{
				pow(aux,r,a);
				copy(a,aux);
			}
			pow(aux,r,r);
			copy(r,aux);
		}
		out<<a[1][1]<<"\n";
	}
	return 0;
}