#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
#include <random>
#include <ctime>
#include <cstring>

using namespace std;

const int maxDim = 4;

struct matrix
{
	int n, m;
	long long elem[maxDim][maxDim];
	long long* operator [](int i)const
	{
		return (long long*)elem[i];
	}
	matrix(int lines, int columns)
	{
		n = lines;
		m = columns;
		memset(elem,0,sizeof(elem));
	};
	matrix(const matrix &that)
	{
		n = that.n;
		m = that.m;
		memcpy(elem,that.elem,sizeof(that.elem));
	}
	matrix operator + (const matrix &that)
	{
		matrix ret = matrix(n, m);
		assert(n == that.n && m == that.m);
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j)
				ret[i][j] = elem[i][j] + that[i][j];
		return ret;
	}
	matrix operator*(const matrix &that)
	{
		assert(m == that.n);
		int p = that.m;
		matrix ret = matrix(n, p);
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= p; ++j)
			{
				ret[i][j] = 0;
				for (int k = 1; k <= m; ++k)
					ret[i][j] += elem[i][k] * that.elem[k][j];
			}
		return ret;
	}
	void operator%=(int MOD)
	{
	    for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j)
                elem[i][j] %= MOD;
	}
};

const int MOD = 666013;

matrix power(matrix base, int exp)
{
    if(exp == 1)
        return base;
    if(exp % 2 == 0)
    {
        matrix x = power(base, exp / 2);
        x = x * x;
        x %= MOD;
        return x;
    }
    matrix x = power(base, exp - 1);
    base = base * x;
    base %= MOD;
    return base;
}

int query(int x, int y, int z, int a, int b, int c, int n)
{
    matrix m(1, 3);
    m[1][1] = x;
    m[1][2] = y;
    m[1][3] = z;

    matrix s(3, 3);
    s[1][1] = 0;
    s[1][2] = 0;
    s[1][3] = c;

    s[2][1] = 1;
    s[2][2] = 0;
    s[2][3] = b;

    s[3][1] = 0;
    s[3][2] = 1;
    s[3][3] = a;

    m = m * power(s, n);
    m %= MOD;
    return m[1][1];
}

int main()
{
    ifstream in("iepuri.in");
    ofstream out("iepuri.out");
    int t, x, y, z, a, b, c, n;
    in >> t;
    for(int i = 1; i <= t; ++i)
    {
        in >> x >> y >> z >> a >> b >> c >> n;
        out << query(x, y, z, a, b, c, n) << "\n";
    }
	return 0;
}