#include <stdio.h>
#include <stdlib.h>
#define MAX 666013

int execution(int x, int y, int z, int a, int b, int c, int n) {
	int tmp;
	for (int i = 0 ; i < n - 2 ; ++i) {
		tmp = z;
		z = a * z + b * y + c * x;
		x = y;
		y = tmp;
		z %= MAX; 
	}
	return z;
}

int main() {
	FILE *in, *out;
	int t, a, b, c, x, y, z, n, result;
	if ((in = fopen("iepuri.in", "rt")) == NULL) {
		printf("Nu am putut deschide fisierul de intrare!\n");
		return -1;
	}
	if ((out = fopen("iepuri.out", "wt")) == NULL) {
		printf("Nu am putut deschide fisierul de iesire!\n");
		return -2;
	}
	fscanf(in, "%d", &t);
	for (int i = 0 ; i < t ; ++i) {
		fscanf(in, "%d %d %d %d %d %d %d", &x, &y, &z, &a, &b, &c, &n);
		result = execution(x, y, z, a, b, c, n);
		fprintf(out, "%d\n", result);
	}
	fclose(in);
	fclose(out);
	return 0;
}