///(0, 1, 0)   (x)   (y)
///(0, 0, 1) * (y) = (z)
///(c, b, a)   (z)   (c * x + b * y + a * z)
///hella nice
#include <fstream>
#define int long long

using namespace std;

ifstream cin ("iepuri.in");
ofstream cout ("iepuri.out");

const int MOD = 666013;
const int N = 10;
int v[N][N], sol[N][N];

int x, y, z, a, b, c, t, n;

void prodmatrix (int a[N][N], int b[N][N], int c[N][N])
{
    int aux[N][N];
    int n = 3;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            aux[i][j] = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 1; k <= n; ++k)
                aux[i][j] = (aux[i][j] + a[i][k] * b[k][j] % MOD) % MOD;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            c[i][j] = aux[i][j];
}

int llpowmatrix (int a[N][N], int fin[N][N], int n)
{
    int res[N][N];
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            res[i][j] = 0;
    for (int i = 1; i <= 3; ++i)
        res[i][i] = 1;
    while (n)
    {
        if (n & 1)
            prodmatrix(res, a, res);
        prodmatrix(a, a, a);
        n /= 2;
    }
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            fin[i][j] = res[i][j];
}

void solve ()
{
    v[1][1] = v[1][3] = v[2][1] = v[2][2] = 0;
    v[1][2] = v[2][3] = 1;
    v[3][1] = c;
    v[3][2] = b;
    v[3][3] = a;
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            sol[i][j] = 0;
    llpowmatrix(v, sol, n - 2);
    //cout << (sol[3][1] * x % MOD + (sol[3][2] * y % MOD + sol[3][3] * z % MOD)) % MOD << '\n';
    cout << "1\n";
}
signed main()
{
    for (cin >> t; t; --t)
    {
        cin >> x >> y >> z >> a >> b >> c >> n;
        solve ();
    }
    return 0;
}