#include <iostream>
#include <fstream>
#define M 666013
#define ull unsigned long long

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
ull A[3][3],
    sol[3][3],
    C[3][3];

void inmultire(ull a[3][3],ull b[3][3])
{
    ull 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])%M;
        }
    }
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)a[i][j]=c[i][j];
}

void putere(ull sol[3][3],int k)
{
    while(k)
    {
        if(k%2==1)inmultire(sol,C),k--;
        else inmultire(C,C),k/=2;
    }
}

int main()
{
    int Q,N;
    fin>>Q;
    for(;Q;Q--)
    {
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                sol[i][j]=C[i][j]=0;
            }
        }
        C[1][0]=C[2][1]=1;
        sol[0][0]=sol[1][1]=sol[2][2]=1;
        fin>>A[0][0]>>A[0][1]>>A[0][2]
           >>C[2][2]>>C[1][2]>>C[0][2]>>N;
        putere(sol,N);
        inmultire(A,sol);
        fout<<A[0][0]<<'\n';
    }
}