#include <fstream>
#include <cstring>
using namespace std;
const int MOD = 666013;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
int B[3][3]={{0,0,9},{1,0,9},{0,1,9}},A[3][3],P[3][3]={{1,0,0},{0,1,0},{0,0,1}};

void inmult(int A[][3], int B[][3]) // A <-- A*B
//inline void inmult(int A[][3], int B[][3], int C[][3])
{
    int C[3][3];
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
        {
            long long s=0;
            for(int k=0; k<3; k++)
                s+=1LL*A[i][k]*B[k][j];
            C[i][j]=s%MOD;
        }
    memcpy(A,C,sizeof(C));
}

int putere(int n)
{
    while(n > 0)
    {
        while(n % 2 == 0)
        {
            inmult(A, A);
            n /= 2;
        }
        inmult(P, A);
        n--;
    }
    return P[0][2];
}

int main()
{
    int T,N;
    f >> T;
    while(T--)
    {
        memcpy(A,B,sizeof(B));
        f>>P[0][0]>>P[0][1]>>P[0][2]>>A[2][2]>>A[1][2]>>A[0][2]>>N;
        g<<putere(N-2)<<'\n';
    }
    f.close();
    g.close();
    return 0;
}