# include <fstream>

# define MODULO 666013

using namespace std;

ifstream fin ("iepuri.in");

ofstream fout ("iepuri.out");
int x,y,z,a,b,c,n,T,Teste;

long long A[5][5],B[5][5],C[5][5];

long long S[5][5],R[5][5];

void inmult (long long A[5][5],long long B[5][5], int na, int ma, int nb, int mb, long long C[5][5])

{

long long ia,ib,ja,jb;

for(ia=1;ia<=na;ia++)

for (jb=1;jb<=mb;jb++)

C[ia][jb]=0;

for (ia=1;ia<=na;ia++)

for (jb=1;jb<=mb;jb++)

{

for (ib=1;ib<=nb;ib++)

{

C[ia][jb]=(C[ia][jb]+(A[ia][ib]*B[ib][jb])%MODULO)%MODULO;

}

}

}

void putere (int x, long long B[5][5])

{

int i,j;

if (x==1)

{

for (i=1;i<=3;i++)

for (j=1;j<=3;j++)

B[i][j]=A[i][j];

return;

}

if(x==2)

{

inmult (A,A,3,3,3,3,B);

return;

}

putere (x/2,B);

for (i=1;i<=3;i++)

for (j=1;j<=3;j++)

C[i][j]=B[i][j];

inmult (C,C,3,3,3,3,B);

if (x%2==1)

{

for (i=1;i<=3;i++)

for (j=1;j<=3;j++)

C[i][j]=B[i][j];

inmult (C,A,3,3,3,3,B);

}

}

int main ()

{

fin>>Teste;

for (T=1;T<=Teste;T++)

{

fin>>S[1][3]>>S[1][2]>>S[1][1];

fin>>a>>b>>c;

fin>>n;

if (n==1)

fout<<x<<'\n';

else if (n==2)

fout<<y<<'\n';

else if (n==3)

fout<<z<<'\n';

else

{

A[1][1]=a;A[1][2]=1;A[3][1]=c;

A[2][1]=b;A[2][3]=1;

putere(n-2,B);

inmult(S,B,1,3,3,3,R);

fout<<R[1][1]<<'\n';

}

}

return 0;

}