#include<fstream>
using namespace std;

# define MOD 666013

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

int N,M[3][3],M_N[3][3],T,I[3],A[3][3];

void inmulteste()
{
	int i,j,k,s;
	for(i=0;i<3;++i)
		for(j=0;j<3;++j)
		{
			s=0;
			for(k=0;k<3;++k)
				s+=A[i][k]*A[k][j], s%=MOD;
			M_N[i][j]=s;
		}
	for(i=0;i<3;++i)
		for(j=0;j<3;++j)
			A[i][j]=M_N[i][j];
}
void inmultestem()
{
	int i,j,k,s;
	for(i=0;i<3;++i)
		for(j=0;j<3;++j)
		{
			s=0;
			for(k=0;k<3;++k)
				s+=A[i][k]*M[k][j], s%=MOD;
			M_N[i][j]=s;
		}
	for(i=0;i<3;++i)
		for(j=0;j<3;++j)
			A[i][j]=M_N[i][j];
}
void putere(int n)
{
	if(n<=1)
		return;
	putere(n/2);
	inmulteste();
	if(n&1)
		inmultestem();
}
int main()
{
	M[0][1]=1, M[1][2]=1;
	f>>T;
	int i,j,s;
	for(;T;--T)
	{
		f>>I[0]>>I[1]>>I[2]>>M[2][2]>>M[2][1]>>M[2][0]>>N;
		N-=2;
		for(i=0;i<3;++i)
			for(j=0;j<3;++j)
				A[i][j]=M[i][j];
		putere(N);
		s=0;
		for(i=0;i<3;++i)
			s+=M_N[2][i]*I[i], s%=MOD;
		g<<s<<'\n';
	}
}