#include    <iostream>
#include    <fstream>

using namespace std;

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

const int MOD = 666013;

long long s, A[3][3], B[3][3], C[3][3];

void creareA(int a, int b, int c){

    A[1][1] = 0; A[1][2] = 1; A[1][3] = 0;
    A[2][1] = 0; A[2][2] = 0; A[2][3] = 1;
    A[3][1] = c; A[3][2] = b; A[3][3] = a;

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

void fun( long long A[3][3], long long B[3][3])
{

    int i, j, k;
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            C[i][j]=0;


    for (i = 1; i <= 3; i++)
        for (j = 1; j <= 3; j++)
            for(k = 1; k <= 3; k++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;

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

}

long long RidicareLogaritmica(long long x)
{
if( x > 1)
    {
        if (x % 2 == 0)
            {
                fun(B,A);
                return RidicareLogaritmica(x / 2);

            }
        else
            {
                fun(A,A);
                return RidicareLogaritmica(x - 1);
            }

    }
}

long long vn(int x, int y, int z)
{
   unsigned long long int s;
   s = ((C[3][1] * x) % MOD + (C[3][2] * y) % MOD + (C[3][3] * z) % MOD) % MOD;
    return s;
}
int main()
{
    int T, x, y, z, a, b, c, n;

     f >> T;
    while (T){

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

        creareA(a, b, c);
        RidicareLogaritmica(n-2);
        g << vn(x, y, z) << "\n";



    T--;
    }

    return 0;
}