#include<stdio.h>

long long m[40][5][5],r[5][5];

void init(int a,int b,int c)
{
m[0][1][1]=m[0][1][3]=m[0][2][1]=m[0][2][2]=0;
m[0][1][2]=m[0][2][3]=1;
m[0][3][1]=c;
m[0][3][2]=b;
m[0][3][3]=a;
}

void add_k(int q)
{
long long a[5][5],b[5][5];
int i,j,k;
for(i=1;i<=3;i++)
  for(j=1;j<=3;j++)
   a[i][j]=r[i][j];
for(i=1;i<=3;i++)
  for(j=1;j<=3;j++)
   b[i][j]=m[q][i][j];

for(i=1;i<=3;i++)
  for(j=1;j<=3;j++)
    {
    r[i][j]=0;
    for(k=1;k<=3;k++)
      r[i][j]+=a[i][k]*b[k][j];
    r[i][j]%=666013;
    }
}


void calc(int s,int d)
{
//ridic m[s] la 2 si scriu in d rezultatul
int i,j,k;

for(i=1;i<=3;i++)
  for(j=1;j<=3;j++)
    {
    m[d][i][j]=0;
    for(k=1;k<=3;k++)
      m[d][i][j]+=m[s][i][k]*m[s][k][j];
    m[d][i][j]%=666013;
    }
}


int main()
{
FILE *fin=fopen("iepuri.in","r");
FILE *fout=fopen("iepuri.out","w");

int n,t,i[5],cnt,a,b,c,k,g,h;
long long sol;

fscanf(fin,"%d",&t);

for(cnt=1;cnt<=t;cnt++)
  {
  fscanf(fin,"%d %d %d %d %d %d %d",&i[1],&i[2],&i[3],&a,&b,&c,&n);
  init(a,b,c);

  //matricea la puterea 2^k
  for(k=1;(long long)(1<<k)<=n;k++)
    calc(k-1,k);

  //matricea rezultat -> r formata din puterile lui 2 prin biti
  k--;
  for(g=1;g<=3;g++)
    for(h=1;h<=3;h++)
      r[g][h]=m[k][g][h];
  k--;

  while(k>=0)
    {
    if((1<<k)&n)
      {//inmultesc si matricea k la rezultat
       add_k(k);
      }
    k--;
    }

  //solutia
  sol=0;
  for(k=1;k<=3;k++)
    sol+=r[1][k]*i[k];
  sol%=666013;

  fprintf(fout,"%d\n",sol);
  }

fcloseall();
return 0;
}