#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int M[4][4],N[4][4],C[4][4];

void Imultire(int t){
    if(t == 1){

        C[1][1] = (M[1][1] * M[1][1] + M[1][2] * M[2][1] + M[1][3] * M[3][1]) % MOD;
        C[1][2] = (M[1][1] * M[1][2] + M[1][2] * M[2][2] + M[1][3] * M[3][2]) % MOD;
        C[1][3] = (M[1][1] * M[1][3] + M[1][2] * M[2][3] + M[1][3] * M[3][3]) % MOD;
        C[2][1] = (M[2][1] * M[1][1] + M[2][2] * M[2][1] + M[2][3] * M[3][1]) % MOD;
        C[2][2] = (M[2][1] * M[1][2] + M[2][2] * M[2][2] + M[2][3] * M[3][2]) % MOD;
        C[2][3] = (M[2][1] * M[1][3] + M[2][2] * M[2][3] + M[2][3] * M[3][3]) % MOD;
        C[3][1] = (M[3][1] * M[1][1] + M[3][2] * M[2][1] + M[3][3] * M[3][1]) % MOD;
        C[3][2] = (M[3][1] * M[1][2] + M[3][2] * M[2][2] + M[3][3] * M[3][2]) % MOD;
        C[3][3] = (M[3][1] * M[1][3] + M[3][2] * M[2][3] + M[3][3] * M[3][3]) % MOD;

    }
    if(t == 2){
        C[1][1] = (M[1][1] * N[1][1] + M[1][2] * N[2][1] + M[1][3] * N[3][1]) % MOD;
        C[1][2] = (M[1][1] * N[1][2] + M[1][2] * N[2][2] + M[1][3] * N[3][2]) % MOD;
        C[1][3] = (M[1][1] * N[1][3] + M[1][2] * N[2][3] + M[1][3] * N[3][3]) % MOD;
        C[2][1] = (M[2][1] * N[1][1] + M[2][2] * N[2][1] + M[2][3] * N[3][1]) % MOD;
        C[2][2] = (M[2][1] * N[1][2] + M[2][2] * N[2][2] + M[2][3] * N[3][2]) % MOD;
        C[2][3] = (M[2][1] * N[1][3] + M[2][2] * N[2][3] + M[2][3] * N[3][3]) % MOD;
        C[3][1] = (M[3][1] * N[1][1] + M[3][2] * N[2][1] + M[3][3] * N[3][1]) % MOD;
        C[3][2] = (M[3][1] * N[1][2] + M[3][2] * N[2][2] + M[3][3] * N[3][2]) % MOD;
        C[3][3] = (M[3][1] * N[1][3] + M[3][2] * N[2][3] + M[3][3] * N[3][3]) % MOD;

    }



    for(int j = 1; j <= 3; j++)
        for(int k = 1; k <= 3; k++)
            M[j][k] = C[j][k];

}


void Logpow( int n){

    if(n <= 1)
        return;
    Logpow(n / 2);
    Imultire(1);
    if(n % 2 != 0)
        Imultire(2);
}


int main()
{
    ios :: sync_with_stdio(false);
    fin.tie(NULL);

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

    fin >> T;

    for(int i = 1; i <= T; i ++){

        fin >> x >> y >> z >> a >> b >> c >> n;

        for(int j = 1; j <= 3; j++)
            for(int k = 1; k <= 3; k++)
                M[j][k] = 0;

        M[1][2] = M[2][3] = 1;
        M[3][1] = c; M[3][2] = b; M[3][3] = a;

        for(int j = 1; j <= 3; j++)
            for(int k = 1; k <= 3; k++)
                N[j][k] = M[j][k];

        Logpow(n - 2);
        fout << (M[3][1] * x + M[3][2] * y + M[3][3] * z) % MOD << "\n";

    }

    return 0;
}