#include <stdio.h>


#define MX 666013

int X,Y,Z,A,B,C,N;

inline int compute(){
	
	int t_1 = Z, t_2 = Y, t_3 = X;
	int i;
	int rabbits = 0;

	for(i = 0;i <= N-3; i++){
		rabbits = (((A*t_3%MX)%MX + (B*t_2%MX)%MX)%MX + (C*t_1%MX)%MX)%MX;
		
		t_3 = t_2;
		t_2 = t_1;
		t_1 = rabbits;
	}
	return rabbits;
}

int main(void){


	FILE *fin;
	FILE *fout;

	
	
	int t;
	int i;

	fin = fopen("iepuri.in","r");

	if(!fin){
		printf("Unable to open input file\n");
		return 1;	
	}

	fout = fopen("iepuri.out","w");

	if(!fout){
		printf("Unable to open output file\n");
		return 1;
	}


	fscanf(fin,"%d",&t);
		
	for(i = 0;i < t; i++){
		fscanf(fin,"%d %d %d %d %d %d %d",&X,&Y,&Z,&A,&B,&C,&N);
		fprintf(fout,"%d\n",compute());
	}
	return 0;
	
}