#include <vector>
#include <fstream>

using namespace std;

ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");


using ll = long long;
using VI = vector < ll > ;
using Matrix = vector < VI >;

const ll  mod = 666013;
const int k = 3;
VI F1;
Matrix T;
Matrix mult( Matrix A, Matrix B);
Matrix pow(Matrix A, int n);
int Fib(int n);
int a,b,c;

int main() {
	
	int n,t;
	fin >> t;
	for ( ; t > 0; --t) {
		F1 = VI(k+1);
		fin >> F1[1] >> F1[2] >> F1[3] >> a >> b >> c >> n;
		fout << Fib(n) << "\n";
	
	}
}

Matrix mult( Matrix A, Matrix B) {
	
	Matrix res ( k + 1, VI ( k+ 1 )) ;
	for ( int i = 1; i <= k ; ++i)
		for ( int j = 1; j <= k ; ++j)
			for ( int w = 1; w <= k; ++w)
				res[i][j] = (res[i][j] + A[i][w] * B[w][j] ) % mod;
	return res;
}

Matrix pow(Matrix A, int p) {
	
	if ( p == 1)
		return A;
	if ( p & 1 )
		return mult(A,pow(A,p-1));
	Matrix X = pow(A,p/2);
	return mult(X,X);	
}

int Fib(int n) {
	
	
	T = Matrix(k+1, vector <ll> (k+ 1) );
	T[1][1] = 0, T[1][2] = 1, T[1][3] = 0;
	T[2][1] = 0, T[2][2] = 0, T[2][3] = 1;
	T[3][1] = c, T[3][2] = b, T[3][3] = a;
	if ( n == 1)
		return 1;
	T = pow(T,n);
	ll res = 0;
	for ( int i = 1; i <= k; ++i)
		res = ( res + T[1][i] * F1[i]) % mod;
	return res;
	
}