#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int main()
{
	int nr, A, B, C, N;
	fin >> nr;
	int v[7];
	for (int i = 1; i <= nr; i++)
	{
		for (int j = 0; j < 6; j++)
		{
			fin >> v[j];
		}
		A = v[3];
		B = v[4];
		C = v[5];
		for (int k = 3; k < 6; k++)
		{
			v[k] = A * v[k - 1] + B * v[k - 2] + C * v[k - 3];
		}
		fin >> N;
		int R = v[N] % 666013;
		fout << R << endl;
	}
	return 0;
}