#include <fstream>
#define MOD 666013
using namespace std;

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

long long int t,n,k,A[3][3],S[3][3],C[3][3] ,B[3][3];
long long int x, y, z, a, b, c , i, j;

void copy(long long int a[3][3],long long int b[3][3])
{
    for(int i = 0; i <= 2; i++)
        for(int j = 0; j <= 2; j++)
            a[i][j] = b[i][j];
}


void inmultire(long long int a[3][3], long long int b[3][3])
{
    long long int c[3][3];
    int i, j, k;
    long long s;
    for(i = 0; i <= 2; i++)
        for(j = 0; j <= 2; j++)
        {
            s = 0;
            for(k = 0; k <= 2; k++)
                s += (1LL* a[i][k] * b[k][j]);
            c[i][j] = s % MOD;
        }
    copy(a, c);
}


void solve()
{
    int i,j,q;
    k = n - 2;
    for(i=0;i<3;i++)
    {
        //S este la inceput I3
        S[i][i]=1;
    }
    A[0][2] = c;A[1][2] = b; A[2][2] = a;
    A[1][0] = A[2][1] = 1;

    while(k)
    {
        if(k % 2 == 1)
        {
            inmultire(S, A);

        }
        inmultire(A, A);
        k = k / 2;
    }
    B[0][0] = x;  B[0][1] = y; B[0][2] = z;
    inmultire(B, S);
    fout << B[0][2]<<"\n";
}

void clean()
{
     for(int i = 0; i <= 2; i++)
        for(int j = 0; j <= 2; j++)
            A[i][j] = B[i][j] = S[i][j] = 0;
}


int main()
{
    fin >> t ;
    while(t--)
    {
         fin >> x >> y >> z >> a >> b >> c >> n;
         clean();
         solve();
    }
    return 0;
}