#include <iostream>
#include <fstream>

using namespace std;

int x,y,z,a,b,c,n,M[4][4],O[4][4],aux[4][4];

int main()
{
    int i,j,R;
    FILE *f=fopen("iepuri.in","r");
    FILE *g=fopen("iepuri.out","w");
    fscanf(f,"%d",&R);
    while(R)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        fscanf(f,"%d %d %d",&M[1][1],&M[1][2],&M[1][3]);
        fscanf(f,"%d",&n);
        M[2][2]=M[2][3]=M[3][1]=M[3][3]=0;
        O[1][2]=O[1][3]=O[2][1]=O[2][3]=O[3][1]=O[3][2]=0;
        O[1][1]=O[2][2]=O[3][3]=1;
        M[2][1]=M[3][2]=1;
        n-=2;
        while(n)
        {
            if(n%2!=0)
            {
                for(i=1;i<=3;i++)
                    for(j=1;j<=3;j++)
                        aux[i][j]=(O[i][1]*M[1][j]+O[i][2]*M[2][j]+O[i][3]*M[3][j])%666013;
                for(i=1;i<=3;i++)
                    for(j=1;j<=3;j++)
                        O[i][j]=aux[i][j];
            }
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    aux[i][j]=(M[i][1]*M[1][j]+M[i][2]*M[2][j]+M[i][3]*M[3][j])%666013;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    M[i][j]=aux[i][j];
            n/=2;
        }

        fprintf(g,"%d\n",((O[1][1]*c)%666013+(O[1][2]*b)%666013+(O[1][3]*a)%666013)%666013);
        R--;
    }
    return 0;
}