#include<cstdio>
#define N 666013
#define lul unsigned long long
lul e[3][3],d[3][3],f[3][3],g[3][3];
int a,b,c,x,y,z,k,t,i,v[80],n;

void mul(lul a[3][3],lul b[3][3],lul c[3][3])
{int i,j,k;
long s;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
      {a[i][j]=0;
      for(k=0;k<3;k++)
             a[i][j]=(a[i][j]+b[i][k]*c[k][j])%N;}}
      
void copy(lul a[3][3],lul b[3][3])
{int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
      a[i][j]=b[i][j];}

int main()
{freopen("iepuri.in","r",stdin);
freopen("iepuri.out","w",stdout);
scanf("%d",&t);
while(t--)
       {scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
       e[0][0]=e[0][2]=0,e[0][1]=1;
       e[1][0]=e[1][1]=0,e[1][2]=1;
       e[2][0]=c,e[2][1]=b,e[2][2]=a;
       mul(d,e,e),k=0,n-=2;
       while(n)
               v[++k]=n&1,n>>=1;
       for(i=k-1;i;i--)
       if(!v[i])
               mul(f,e,d),mul(g,e,e),copy(d,f),copy(e,g);
       else
               mul(f,e,d),mul(g,d,d),copy(e,f),copy(d,g);
       printf("%d\n",(int)(e[2][0]*x+e[2][1]*y+e[2][2]*z)%N);}
return 0;}