#include <fstream>

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int a1,b1,c1,d1,e1,f1,g1,h1,i1,x,y,z,aa,bb,cc,n,prim=666013;
void Putere(int &a,int &b,int &c,int &d,int &e,int &f,int &g,int &h,int &i,int k)
{ int a2=a,b2=b,c2=c,d2=d,e2=e,f2=f,g2=g,h2=h,i2=i;
  int a3,b3,c3,d3,e3,f3,g3,h3,i3;
  if(k>1)
    if(k%2==1) {Putere(a,b,c,d,e,f,g,h,i,k-1);
                a3=a;b3=b;c3=c;d3=d;e3=e;f3=f;g3=g;h3=h;i3=i;
                a=((1LL*a2*a3)%prim+(1LL*b2*d3)%prim+(1LL*c2*g3)%prim)%prim;
                b=((1LL*a2*b3)%prim+(1LL*b2*e3)%prim+(1LL*c2*h3)%prim)%prim;
                c=((1LL*a2*c3)%prim+(1LL*b2*f3)%prim+(1LL*c2*i3)%prim)%prim;
                d=((1LL*d2*a3)%prim+(1LL*e2*d3)%prim+(1LL*f2*g3)%prim)%prim;
                e=((1LL*d2*b3)%prim+(1LL*e2*e3)%prim+(1LL*f2*h3)%prim)%prim;
                f=((1LL*d2*c3)%prim+(1LL*e2*f3)%prim+(1LL*f2*i3)%prim)%prim;
                g=((1LL*g2*a3)%prim+(1LL*h2*d3)%prim+(1LL*i2*g3)%prim)%prim;
                h=((1LL*g2*b3)%prim+(1LL*h2*e3)%prim+(1LL*i2*h3)%prim)%prim;
                a=((1LL*g2*c3)%prim+(1LL*h2*f3)%prim+(1LL*i2*i3)%prim)%prim;
               }
    else
    {
    a=((1LL*a2*a2)%prim+(1LL*b2*d2)%prim+(1LL*c2*g2)%prim)%prim;
    b=((1LL*a2*b2)%prim+(1LL*b2*e2)%prim+(1LL*c2*h2)%prim)%prim;
    c=((1LL*a2*c2)%prim+(1LL*b2*f2)%prim+(1LL*c2*i2)%prim)%prim;
    d=((1LL*d2*a2)%prim+(1LL*e2*d2)%prim+(1LL*f2*g2)%prim)%prim;
    e=((1LL*d2*b2)%prim+(1LL*e2*e2)%prim+(1LL*f2*h2)%prim)%prim;
    f=((1LL*d2*c2)%prim+(1LL*e2*f2)%prim+(1LL*f2*i2)%prim)%prim;
    g=((1LL*g2*a2)%prim+(1LL*h2*d2)%prim+(1LL*i2*g2)%prim)%prim;
    h=((1LL*g2*b2)%prim+(1LL*h2*e2)%prim+(1LL*i2*h2)%prim)%prim;
    a=((1LL*g2*c2)%prim+(1LL*h2*f2)%prim+(1LL*i2*i2)%prim)%prim;
    Putere(a,b,c,d,e,f,g,h,i,k/2);
    }
}
int main()
{ int t;fin>>t;
  for(int i=1;i<=t;i++)
  { fin>>x>>y>>z>>aa>>bb>>cc>>n;
    a1=b1=e1=g1=0;
    d1=h1=1;
    c1=cc;
    f1=bb;
    i1=aa;
    Putere(a1,b1,c1,d1,e1,f1,g1,h1,i1,n-2);
fout<<((1LL*x*c1)%prim+(1LL*y*b1)%prim+(1LL*z*a1)%prim)%prim<<"\n";
  }

    return 0;
}