#include<fstream>
#define inf "iepuri.in"
#define outf "iepuri.out"
#define MOD 666013
using namespace std;

fstream f(inf,ios::in),g(outf,ios::out);

int T, X, Y, Z, A, B, C, N; long long s;
int AA[4][4], AN[4][4], I[4], aux[4][4];

void m(int A1[4][4], int A2[4][4])
{
	for(int i=1; i<=3; i++)
		for(int j=1; j<=3; j++)
		{			
			s = 0;
			for(int k=1; k<=3; k++) s += (long long)(A1[i][k]*A2[k][j]) % MOD, s %= MOD;
			aux[i][j] = s;
		}
	for(int i=1; i<=3; i++)
		for(int j=1; j<=3; j++) A1[i][j] = aux[i][j];
}

void explog(int n)
{
	if( n<=1 ) return;
	explog( n/2 );
	m(AN, AN);
	if( n&1 ) m(AN, AA);
}

void solve()
{
	AA[2][1] = 1; AA[3][2] = 1;	
	f>>T;
	for(; T; T--)
	{
		f>>X>>Y>>Z>>A>>B>>C>>N;
		AA[1][1] = A; AA[1][2] = B; AA[1][3] = C; 
		I[3] = X; I[2] = Y; I[1] = Z;

		for(int i=1; i<=3; i++)
			for(int j=1; j<=3; j++) AN[i][j] = AA[i][j];
		
		explog(N-2);
		
		s = 0;
		for(int i=1; i<=3; i++) s += (long long)( AN[1][i]*I[i] ) % MOD , s %= MOD;
		g<< s <<"\n";
	}
}

int main()
{
	solve();
	f.close(); g.close();
	return 0;
}