#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

ifstream f("iepuri.in") ;
ofstream g("iepuri.out") ;

int A[3][3], B[3][3], C[3][3];
int Z0, Z2, Z1;
void read()
{
    int i, j;
    for(i = 1; i <= 3; i++)
        for(j = 1; j <= 3; j++) A[i][j] = 0 ;
    f>>A[1][1]>>A[1][2]>>A[1][3];
    A[2][1] = 1;
    A[3][2] = 1;

    for(i = 1; i <= 3; i++)
        for(j = 1; j <=3; j++) B[i][j] = A[i][j];

}

void multiply_m(int D[3][3], int E[3][3])
{
    int i, j, k, s;
    for(i = 1; i <= 3; i++)
    {
        for(j = 1; j <= 3; j++)
        {
            s = 0;
            for(k = 1; k <= 3; k++)
                {s += (D[i][k] * E[k][j]) % MOD;
                 s %= MOD;
                }
            C[i][j] = s;

        }
    }
    for(i = 1; i <= 3; i++)
        for(j = 1; j <= 3; j++)
            A[i][j] = C[i][j];
}
void putere( int p)
{
    if(p == 1) return;
    if(p == 2)
        multiply_m(A,A) ;
    else if(p%2 == 0)
    {
        putere(p/2);
        multiply_m(A,A);
    }
    else if(p%2 == 1){
        putere(p/2);
        multiply_m(A,A);
        multiply_m(B,A);
    }

}
int main()
{
    int n, p;
    f>>n;
    int Z0, Z2, Z1;
    for(int i = 1; i <= n; i++)
   {
    f>>Z0>>Z1>>Z2;
    read();
    f>>p;
    putere(p - 2);
    int x = Z2 * A[1][1] + Z1 * A[1][2] + Z0 * A[1][3];
    g<<x<<endl;
   }
return 0 ;
}