#include <stdio.h>
FILE *fi, *fo;
int x, y, z, a, b, c;
int t, k;
long long n, i, v[3], zcur;
int main (void) {
	fi=fopen("iepuri.in", "rt");
	fo=fopen("iepuri.out", "wt");
	fscanf(fi, "%d", &t);
	for (k=1; k<=t; k++) {
	fscanf(fi, "%d %d %d %d %d %d %lld", &x, &y, &z, &a, &b, &c, &n);
	v[0]=x;
	v[1]=y;
	v[2]=z;
	for (i=3; i<=n; i++) {
	zcur=a*v[2]+b*v[1]+c*v[0];
	v[0]=v[1];
	v[1]=v[2];
	v[2]=zcur;
	}
	fprintf (fo, "%lld\n", zcur%666013);
	}
	fclose(fi);
	fclose(fo);
return 0;
}