#include <fstream>

using namespace std;

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

long long n;
const int mod = 666013;

int y[4][4];
int x[4];
int z[4][4];

void inmultire(int m1[4][4], int m2[4][4])
{
	int aux[4][4]={0};
	for(int i=1;i<=3;i++)
		for (int j = 1; j <= 3; j++)
			for (int k = 1; k <= 3; k++)
				aux[i][j] += (m1[i][k] * m2[k][j])%mod;
    for(int i=1;i<=3;i++)
		for (int j = 1; j <= 3; j++)
            z[i][j]=aux[i][j]%mod;
}

void putere(long long p)
{
	if (p == 1)
		{
		    for(int i=1;i<=3;i++)
                for (int j = 1; j <= 3; j++)
                    z[i][j]=y[i][j];
		}
    else
    {
		if (p % 2 == 0)
		{
			putere(p / 2);
            inmultire(z,z);

		}
		else
		{
			putere(p - 1);
			inmultire(y, z);

		}
    }
}

int main()
{
	int t;
	fin >> t;
	y[2][1] = 1;
    y[3][2] = 1;
	for (int i = 1; i <= t; i++)
	{
		int a, b, c, n;
		fin >> x[1]>> x[2] >> x[3] >> a >> b >> c >> n;
		y[1][3] = c;
		y[2][3] = b;
		y[3][3] = a;
		putere(n-2);
		fout << (x[1] * z[1][3]+ x[2] * z[2][3]+ x[3] * z[3][3])%mod<<'\n';
	}
	return 0;
}