#include <iostream>
#include <fstream>
#define NMAX 666013
#define ll long long
using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

ll M[3][3], P[3][3], aux[3][3];

void copy(ll A[3][3], ll B[3][3]) {
	int i,j;

	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++)
			A[i][j] = B[i][j];
}

void mult(ll A[3][3], ll B[3][3]) {
	int i,j,k;
	ll sum;

	for(i = 0; i < 3; i++)
		for(j = 0; j < 3; j++) {
			sum = 0;
			for(k = 0; k < 3; k++)
				sum += (A[i][k]*B[k][j])%NMAX;
			aux[i][j] = sum%NMAX;
		}
}

int exp(int A, int B, int C, int n) {
	int i,p,h,j,k;

	n -= 2;
	M[0][0] = A, M[0][1] = B, M[0][2] = C;
	M[1][0] = 1, M[1][1] = 0, M[1][2] = 0;
	M[2][0] = 0, M[2][1] = 1, M[2][2] = 0;

	P[0][0] = 1, P[0][1] = 0, P[0][2] = 0;
	P[1][0] = 0, P[1][1] = 1, P[1][2] = 0;
	P[2][0] = 0, P[2][1] = 0, P[2][2] = 1;

	for(i = 0; (1<<i) <= n; i++) {
		if((1<<i) & n) {
			mult(P,M);
			copy(P,aux);
		}
		mult(M,M);
		copy(M,aux);
	}
}


int main() {
	ll X,Y,Z,A,B,C,n,T;
	int i;

	f>>T;
	for(i = 0; i < T; i++) {
		f>>X>>Y>>Z>>A>>B>>C>>n;
		exp(A,B,C,n);
		g<<P[0][0]*Z+P[0][1]*Y+P[0][2]*X<<"\n";
	}

	return 0;
}