#include <iostream>
#include <fstream>
using namespace std;

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