//#include "stdafx.h"
#include <cstdio>
//#include <conio.h>
#include <cstring>
#define REST 666013
typedef long long mat22[3][3];
long long v[3],vr[3];
mat22 mi,mu={{1,0,0},{0,1,0},{0,0,1}},rezultat;
void scriere(mat22 a) {
	for(int i=0; i<3; i++) {
		for(int j=0; j<3; j++)
			printf("%ld ",a[i][j]);
		printf("\n");
	}
}

void inmultire(mat22 a,mat22 b, mat22 c) {
	int i,j,k;
	for(i=0; i<3; i++) 
		for(j=0; j<3;j++) {
			c[i][j]=0;
			for(k=0; k<3; k++)
				c[i][j]=(c[i][j]+(a[i][k]*b[k][j]%REST))%REST;
		}
}

void putere(long long k, mat22 a) {
	long long exponent=k;
	int lt=sizeof(mat22);
	mat22 baza,rez,rez2;
	//printf("%d\n",lt);
	memcpy(baza,a,lt);
	while(exponent>0) {
		while(!(exponent%2)) {
			inmultire(baza,baza,rez);
			//scriere(rez);
			memcpy(baza,rez,lt);
			exponent>>=1;
		}
		exponent--;
		inmultire(rezultat,baza,rez2);
		memcpy(rezultat,rez2,lt);
	}
	//scriere(rezultat);
}

void inmultirev() {
	for(int i=0; i<3; i++) {
		vr[i]=0;
		for(int j=0; j<3; j++)
			vr[i]=(vr[i]+(rezultat[i][j]*v[j])%REST)%REST;
	}
}


int main()
{
	mi[1][0]=1LL;
	mi[2][1]=1LL;
	long long n;
	long long x,y,z, a,b,c,t,i;
	FILE *f=fopen("iepuri.in","r");
	FILE *g=fopen("iepuri.out","w");
	fscanf(f,"%lld",&t);
	for(i=0; i<t; i++) {
		memcpy(rezultat,mu,sizeof(mi));
		fscanf(f,"%lld %lld %lld %lld %lld %lld %lld",&v[2],&v[1],&v[0],&a,&b,&c,&n);
		mi[0][0]=a;
		mi[0][1]=b;
		mi[0][2]=c;
		putere(n-2,mi);
		inmultirev();
		fprintf(g,"%lld\n",vr[0]);
	}
	fclose(f);
	fclose(g);
	return 0;
}