#include<stdio.h>

FILE *f = fopen("iepuri.in","r");
FILE *g = fopen("iepuri.out","w");

#define MaxMat 5
#define Mod 666013

int T,N,I0,I1,I2;
int M[MaxMat][MaxMat],I[MaxMat][MaxMat];

void citire(void)
{
    fscanf(f,"%d %d %d %d %d %d %d",&I0,&I1,&I2
        ,&M[3][3],&M[3][2],&M[3][1],&N);
}

void initializare(void)
{
    M[1][1] = M[1][3] = M[2][1] = M[2][2] = 0;
    M[1][2] = M[2][3] = 1;

    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            I[i][j] = 0;

    I[1][1] = I[2][2] = I[3][3] = 1;
}

void Mul(int A[MaxMat][MaxMat],int B[MaxMat][MaxMat])
{
    int C[MaxMat][MaxMat];

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

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

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

inline int valoareFinala(void)
{
    initializare();

    N -= 2;

    for(int i=0;(1<<i) <= N;i++)
    {
        if(N & (1<<i))
            Mul(I,M);
        Mul(M,M);
    }

    return (1LL*I0*I[3][1]+1LL*I1*I[3][2]+1LL*I2*I[3][3])%Mod;
}

int main()
{
    fscanf(f,"%d",&T);
    for(int i=1;i<=T;i++)
    {
        citire();
        fprintf(g,"%d\n",valoareFinala());
    }
}