#include<cstdio>
#include<fstream>
#include<iostream>
using namespace std;

int D[3],A,B,C,N,T,mod=666013,power(int);

void read(),solve(),mult(int A[3][3],int B[3][3]);

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("iepuri.in","r",stdin);
	freopen("iepuri.out","w",stdout);
	scanf("%d",&T);
}

void solve()
{
	//ifstream fin("iepuri.in");
	//ofstream fout("iepuri.out");
	for(;T--;)
	{
		//scanf("%d%d%d%d%d%d%d",&D[0],&D[1],&D[2],&A,&B,&C,&N);
		cin>>D[0]>>D[1]>>D[2]>>A>>B>>C>>N;
		if(N<=3)cout<<D[N-1]<<'\n';//printf("%d\n",D[N-1]);
		else cout<<power(N-2)<<'\n';// printf("%d\n",power(N-2));
	}
}

int power(long long p)
{
	int sol[3][3]={{1,0,0},{0,1,0},{0,0,1}},ans=0;
	int M[3][3]={{A,B,C},{1,0,0},{0,1,0}};
	for(int i=0;(1LL<<i)<=p;i++)
	{
		if((1<<i)&p)
			mult(sol,M);
		mult(M,M);
	}
	for(int i=0;i<3;i++)
		ans=(ans+1LL*sol[0][i]*D[2-i]%mod)%mod;
	return ans;
}

void mult(int A[3][3],int B[3][3])
{
	int aux[3][3]={{0,0,0},{0,0,0},{0,0,0}};
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			for(int k=0;k<3;k++)
				aux[i][j]=(aux[i][j]+1LL*A[i][k]*B[k][j]%mod)%mod;
	for(int i=0;i<3;i++)
		for(int j=0;j<3;j++)
			A[i][j]=aux[i][j];
}