#include <bits/stdc++.h>

using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
long long a,b,c,i,j,ii,sol[5][5],suma,i2;
const long long modu=666013;
void inmultire_matrici (long long a1[5][5],long long b[5][5])
{
	for(i=1;i<=3;++i)
		for(j=1;j<=3;++j)
		{
			suma=0;
			for(i2=1;i2<=3;++i2)
				suma=(suma+a1[i][i2]*b[i2][j])%666013;
			sol[i][j]=suma;
		}
	for(i=1;i<=3;++i)
		for(j=1;j<=3;++j)
			a1[i][j]=sol[i][j];
}
void build_matnull (long long a1[5][5])
{
	for (i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            if(i==j)
                a1[i][j]=1;
            else
                a1[i][j]=0;
}
void build_a (long long a1[5][5])
{
	a1[1][1]=a;a1[1][2]=b;a1[1][3]=c;
	for(i=2;i<=3;++i)
		for(j=1;j<=3;++j)
			if(j==i-1)
				a1[i][j]=1;
			else
				a1[i][j]=0;
}
void exponentiere_log (long long matrice[5][5],long long a1[5][5],long long p)
{
	for(ii=0;p>0;++ii)
	{
		if((p & (1<<ii))!=0)
			p-=(1<<ii),inmultire_matrici(matrice,a1);
		inmultire_matrici(a1,a1);
	}
}
int main ()
{
	long long t,x[5],n,mat1[5][5],mat2[5][5],ans;
	fin>>t;
	while(t--)
	{
		fin>>x[1]>>x[2]>>x[3]>>a>>b>>c>>n;++n;
		if(n-3==1)
		{
            ans=0;
            ans=ans+(a*x[3]+b*x[2]+c*x[1])%666013;
            fout<<ans<<"\n";
            continue;
		}
		build_matnull(mat1);build_a(mat2);ans=0;
		exponentiere_log(mat1,mat2,n-3);
		for(i=1;i<=3;++i)
			ans=(ans+(mat1[1][i]*x[4-i])%666013)%666013;
		fout<<ans<<"\n";
	}
	return 0;
}