#include <bits/stdc++.h>

using namespace std;

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

const int MOD = 666013;

long long V[3][3], Z[3][3], D, T;

void Multiply(long long A[3][3], long long B[3][3])
{
    long long C[3][3];

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            C[i][j] = 0;
            for(int k = 0; k < 3; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
        }
    }

    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            A[i][j] = C[i][j];
}

int main()
{
    fin >> T;

    while(T--) {
        for(int i = 0; i < 3; i++)
            fin >> V[0][i];

        for(int i = 2; i >= 0; i--)
            fin >> Z[i][2];

        Z[1][0] = Z[2][1] = 1;

        fin >> D;
        D -= 2;

        while(D) {
            if(D % 2)
                Multiply(V, Z);

            Multiply(Z, Z);
            D /= 2;
        }

        fout << V[0][2] << '\n';

        memset(Z, 0, sizeof(Z));
    }

    fin.close();
    fout.close();

    return 0;
}