#include<fstream>
#define mod 666013

using  namespace std;

struct matrice{
	long a;
	long b;
	long c;
	
	long d;
	long e;
	long f;
	
	long g;
	long h;
	long k;
};
matrice times(matrice A,matrice B)
{
	matrice aux;
	
	aux.a = (((A.a%mod)*(B.a%mod))%mod+((A.b%mod)*(B.d%mod))%mod+((A.c%mod)*(B.g%mod))%mod)%mod;
	aux.b = (((A.a%mod)*(B.b%mod))%mod+((A.b%mod)*(B.e%mod))%mod+((A.c%mod)*(B.h%mod))%mod)%mod;
	aux.c = (((A.a%mod)*(B.c%mod))%mod+((A.b%mod)*(B.f%mod))%mod+((A.c%mod)*(B.k%mod))%mod)%mod;
	
	aux.d = (((A.d%mod)*(B.a%mod))%mod+((A.e%mod)*(B.d%mod))%mod+((A.f%mod)*(B.g%mod))%mod)%mod;
	aux.e = (((A.d%mod)*(B.b%mod))%mod+((A.e%mod)*(B.e%mod))%mod+((A.f%mod)*(B.h%mod))%mod)%mod;
	aux.f = (((A.d%mod)*(B.c%mod))%mod+((A.e%mod)*(B.f%mod))%mod+((A.f%mod)*(B.k%mod))%mod)%mod;
	
	aux.g = (((A.g%mod)*(B.a%mod))%mod+((A.h%mod)*(B.d%mod))%mod+((A.k%mod)*(B.g%mod))%mod)%mod;
	aux.h = (((A.g%mod)*(B.b%mod))%mod+((A.h%mod)*(B.e%mod))%mod+((A.k%mod)*(B.h%mod))%mod)%mod;
	aux.k = (((A.g%mod)*(B.c%mod))%mod+((A.h%mod)*(B.f%mod))%mod+((A.k%mod)*(B.k%mod))%mod)%mod;

return aux;
}	
matrice power(matrice Z,long p)
{
	if(p == 1)return Z;
	else if(p %2 != 0) return times(Z,power(Z,p-1));
	else{
		matrice aux;
		aux = power(Z,p/2);
	 return times(aux,aux);
	}
}
long x,y,z,A,B,C,n,t;
int main()
{
	ifstream fin("iepuri.in");
	ofstream fout("iepuri.out");
	int i;
	matrice Zk,Z,M1,Mf;
	fin>>t;
	for(i = 1; i <= t; i++)
	{
		fin>>x>>y>>z>>A>>B>>C>>n;
	    Z.a = Z.c = Z.d = Z.e = 0;
		Z.b = Z.f = 1;
		Z.g = C;
	    Z.h = B;
	    Z.k = A;
	    M1.a = x;
	    M1.d = y;
	    M1.g = z;
	M1.b=  M1.e = M1.h= M1.c = M1.f = M1.f = M1.k = 0;
	
	Zk = power(Z,n-1);
	
	Mf = times(Zk,M1);
	
fout<<Mf.d<<"\n";
}
fin.close();
fout.close();

return 0;
}