#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
const int MOD = 666013;
int B[3][3]={{0,0,9},{1,0,9},{0,1,9}},A[3][3],P[3][3];
void mul(int A[][3],int B[][3])
{
    int C[3][3];
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
    {
        long long x=0;
        for(int k=0;k<3;k++)
            x+=((long long)A[i][k])*B[k][j];
        C[i][j]=x%MOD;
    }
    memcpy(A,C,sizeof(C));
}
void putere(int n)
{
    while(n>0)
    {
        if(n%2==0)
        {
            mul(A,A);
            n/=2;
        }
        else
        {
            mul(P,A);
            n--;
        }
    }
}
int main()
{
    int T,N;
    f>>T;
    while(T--)
    {
        memcpy(A,B,sizeof(B));///A=B((0,0,9),(1,0,9),(0,1,9))
        f>>P[0][0]>>P[0][1]>>P[0][2];///X Y Z si P e o matrice cu prima linie (x,y,z)
        f>>A[2][2]>>A[1][2]>>A[0][2];///A B C
        f>>N;
        putere(N-2);
        g<<P[0][2]<<'\n';
    }



}