#include<fstream>
#define MOD 666013
using namespace std;
int T,n;
long long A[4],B[4][4],aux[4],aux2[4][4];

inline void LgPut(int put)
{
	int i,j,k;
	while(put)
	{
		if(put%2==1)
		{
			for(i=1;i<=3;i++)
			{
				for(j=1;j<=3;j++)
				{
					aux[i]+=(A[j]*B[j][i])%MOD;
					if(aux[i]>=MOD)
						aux[i]-=MOD;
				}
			}
			for(i=1;i<=3;i++)
			{
				A[i]=aux[i];
				aux[i]=0;
			}
			put--;
		}
		for(i=1;i<=3;i++)
		{
			for(j=1;j<=3;j++)
			{
				for(k=1;k<=3;k++)
				{
					aux2[i][j]+=(B[i][k]*B[k][j])%MOD;
					if(aux2[i][j]>=MOD)
						aux2[i][j]%=MOD;
				}
			}
		}
		for(i=1;i<=3;i++)
		{
			for(j=1;j<=3;j++)
			{
				B[i][j]=aux2[i][j];
				aux2[i][j]=0;
			}
		}
		put/=2;
	}
}

int main()
{
	int i,j;
	ifstream fin("iepuri.in");
	ofstream fout("iepuri.out");
	fin>>T;
	while(T--)
	{
		fin>>A[1]>>A[2]>>A[3];
		fin>>B[3][3]>>B[2][3]>>B[1][3];
		fin>>n;
		B[2][1]=B[3][2]=1LL;
		LgPut(n-2);
		fout<<A[3]<<"\n";
		for(i=1;i<=3;i++)
			for(j=1;j<=3;j++)
				B[i][j]=0LL;
	}
	fin.close();
	fout.close();
	return 0;
}