#include <bits/stdc++.h>

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
const int mod = 666013;
int T, X,Y,Z,A,B,C,N, a[5][5], b[5][5], v[5][5], z[5][5];
void copiere(int x[5][5], int y[5][5])
{
    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            x[i][j] = y[i][j];
}
void inmultire(int x[5][5], int y[5][5])
{
    int c[5][5];
    long long s = 0;
    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
        {
            s = 0;
            for(int k = 1; k <= 3; ++k)
                s += (1LL*x[i][k]*y[k][j]);
            c[i][j] = s % mod;
        }
    copiere(x, c);
}
void lgput(int k)
{
    b[2][1] = b[3][2] = 1;
    b[1][3] = C;
    b[2][3] = B;
    b[3][3] = A;
    v[1][1] = v[2][2] = v[3][3] = 1;
    while(k)
    {
        if(k & 1)
        {
            --k;
            inmultire(v, b);
        }
        inmultire(b, b);
        k /= 2;
    }
}
int main()
{
    fin >> T;
    while(T--)
    {
        fin >> X >> Y >> Z >> A >> B >> C >> N;
        copiere(a, z);
        copiere(b, z);
        copiere(v, z);
        lgput(N - 2);
        a[1][1] = X;
        a[1][2] = Y;
        a[1][3] = Z;
        inmultire(a, v);
        fout << a[1][3] << "\n";
    }
    return 0;
}