#include <fstream>

using namespace std;

ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");

const long long mod = 666013;

int t, n;

struct matrice	{
	long long m[4][4];
} a, b;

matrice inmultire(matrice x, matrice y)	 {
  matrice ans;
  for (int i = 1; i <= 3; ++i)	{
		for (int j = 1; j <= 3; ++j)	{
			ans.m[i][j] = 0;
			for (int k = 1; k <= 3; ++k)	{
				ans.m[i][j] += x.m[i][k] * y.m[k][j];
				ans.m[i][j] %= mod;
			}
		}
  }
  return ans;
}

matrice lgput(matrice baza, int e)	{
	matrice aux;
	aux.m[1][2] = aux.m[1][3] = aux.m[2][1] = aux.m[2][3] = aux.m[3][1] = aux.m[3][2] = 0;
	aux.m[1][1] = aux.m[2][2] = aux.m[3][3] = 1;
	if (e == 0)	 {
		return aux;
	}
  if (e & 1)	{
		aux = baza;
  }
  matrice ans = lgput(baza, e / 2);
  return (inmultire(inmultire(ans, aux), ans));
}


int main()	{
  fin >> t;
  while (t--)	 {
		fin >> a.m[1][1] >> a.m[1][2] >> a.m[1][3];
		a.m[2][1] = a.m[2][2] = a.m[2][3] = a.m[3][1] = a.m[3][2] = a.m[3][3] = 0;
    fin >> b.m[3][3] >> b.m[2][3] >> b.m[1][3];
    b.m[1][1] = b.m[1][2] = b.m[2][2] = b.m[3][1] = 0;
    b.m[2][1] = b.m[3][2] = 1;
    fin >> n;
    b = lgput(b, n - 2);
    b = inmultire(a, b);
    fout << b.m[1][3] << '\n';
  }
}