#include<stdio.h>
#define N 666013
long long e[3][3],d[3][3],f[3][3],g[3][3],n,r;
int a,b,c,x,y,z,k,t,i,j,v[80];
void mul(long long a[3][3],long long b[3][3],long long c[3][3])
{int i,j,k;
long long s;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
      {s=0;
      for(k=0;k<3;k++)
             s=((s%N)+((b[i][k]%N)*(c[k][j]%N))%N)%N;
      a[i][j]=s;}}
      
void copy(long long a[3][3],long long 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%ld",&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]=z,e[2][1]=y,e[2][2]=x;
       mul(d,e,e),k=0,n-=2;
       while(n)
               v[++k]=n%2,n/=2;
       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);
       r=(((e[2][0]%N)*a)%N+((e[2][1]%N)*b)%N+((e[2][2]%N)*c)%N)%N;
       printf("%ld\n",r);}
return 0;}