#include <fstream>

using namespace std;

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

const int r=666013;
int n,N,x1,x2,x3,a,b,c,X[4][4],rez[4][4];

void inmultire(int A[4][4],int B[4][4]){
	int i,j,k,C[4][4];
	for(i=1;i<=3;i++){
		for(j=1;j<=3;j++){
			C[i][j] = 0;
			for(k=1;k<=3;k++){
				C[i][j] = (C[i][j] + (long long)A[i][k]*B[k][j]%r)%r;
			}
		}
	}
	for(i=1;i<=3;i++){
		for(j=1;j<=3;j++){
			A[i][j]=C[i][j];
		}
	}
}

void prelucrare(){
	int i,j;
	n=n-2;
	X[1][1]=a;
	X[1][2]=b;
	X[1][3]=c;
	X[2][1]=1;
	X[2][2]=0;
	X[2][3]=0;
	X[3][1]=0;
	X[3][2]=1;
	X[3][3]=0;
	for(i=1;i<=3;i++){
		for(j=1;j<=3;j++){
			if(i==j){
				rez[i][j]=1;
			}
			else{
				rez[i][j]=0;
			}
		}
	}
	while(n!=0){
        if(n%2!=0){
            inmultire(rez,X);
        }
        inmultire(X,X);
        n=n/2;
    }
	out<<((long long)rez[1][1]*x3%r+(long long)rez[1][2]*x2%r+(long long)rez[1][3]*x1%r)%r<<" ";
}

int main(){
	int i;
	in>>N;
	for(i=1;i<=N;i++){
		in>>x1>>x2>>x3>>a>>b>>c>>n;
		prelucrare();
	}
	return 0;
}