#include <iostream>
#include <fstream>
#define m 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
long long z1=0,z2=0,z3,z4=1,z5=0,z6,z7=0,z8=1,z9,
 a1=0,a2=0,a3,a4=1,a5=0,a6,a7=0,a8=1,a9,x,y,z,A,B,C,t,i,
 aux1,aux2,aux3,aux4,aux5,aux6,aux7,aux8,aux9;

void ridicare(long long n)
{
    if(n!=1)
    {
        if(n%2==0)
        {
            ridicare(n/2);
            aux1=((z1*z1)%m+(z2*z4)%m)%m+(z3*z7)%m;
           aux2=((z1*z2)%m+(z2*z5)%m)%m+(z3*z8)%m;
           aux3=((z1*z3)%m+(z2*z6)%m)%m+(z3*z9)%m;
           aux4=((z4*z1)%m+(z5*z4)%m)%m+(z6*z7)%m;
           aux5=((z4*z2)%m+(z5*z5)%m)%m+(z6*z8)%m;
           aux6=((z4*z3)%m+(z5*z6)%m)%m+(z6*z9)%m;
           aux7=((z7*z1)%m+(z8*z4)%m)%m+(z9*z7)%m;
           aux8=((z7*z2)%m+(z8*z5)%m)%m+(z9*z8)%m;
           aux9=((z7*z3)%m+(z8*z6)%m)%m+(z9*z9)%m;
            z1=aux1%m;
            z2=aux2%m;
            z3=aux3%m;
            z4=aux4%m;
            z5=aux5%m;
            z6=aux6%m;
            z7=aux7%m;
            z8=aux8%m;
            z9=aux9%m;
        }
        else
        {
            ridicare((n-1)/2);
          aux1=((z1*z1)%m+(z2*z4)%m)%m+(z3*z7)%m;
           aux2=((z1*z2)%m+(z2*z5)%m)%m+(z3*z8)%m;
           aux3=((z1*z3)%m+(z2*z6)%m)%m+(z3*z9)%m;
           aux4=((z4*z1)%m+(z5*z4)%m)%m+(z6*z7)%m;
           aux5=((z4*z2)%m+(z5*z5)%m)%m+(z6*z8)%m;
           aux6=((z4*z3)%m+(z5*z6)%m)%m+(z6*z9)%m;
           aux7=((z7*z1)%m+(z8*z4)%m)%m+(z9*z7)%m;
           aux8=((z7*z2)%m+(z8*z5)%m)%m+(z9*z8)%m;
           aux9=((z7*z3)%m+(z8*z6)%m)%m+(z9*z9)%m;
            z1=aux1%m;
            z2=aux2%m;
            z3=aux3%m;
            z4=aux4%m;
            z5=aux5%m;
            z6=aux6%m;
            z7=aux7%m;
            z8=aux8%m;
            z9=aux9%m;
            aux1=((z1*a1)%m+(z2*a4)%m)%m+(z3*a7)%m;
           aux2=((z1*a2)%m+(z2*a5)%m)%m+(z3*a8)%m;
           aux3=((z1*a3)%m+(z2*a6)%m)%m+(z3*a9)%m;
           aux4=((z4*a1)%m+(z5*a4)%m)%m+(z6*a7)%m;
           aux5=((z4*a2)%m+(z5*a5)%m)%m+(z6*a8)%m;
           aux6=((z4*a3)%m+(z5*a6)%m)%m+(z6*a9)%m;
           aux7=((z7*a1)%m+(z8*a4)%m)%m+(z9*a7)%m;
           aux8=((z7*a2)%m+(z8*a5)%m)%m+(z9*a8)%m;
           aux9=((z7*a3)%m+(z8*a6)%m)%m+(z9*a9)%m;
            z1=aux1%m;
            z2=aux2%m;
            z3=aux3%m;
            z4=aux4%m;
            z5=aux5%m;
            z6=aux6%m;
            z7=aux7%m;
            z8=aux8%m;
            z9=aux9%m;
        }
    }

}
int main()
{
    long long n;
    fin>>t;
    for(i=1;i<=t;i++)
    {
      fin>>x>>y>>z>>A>>B>>C>>n;
      z1=0;z2=0;z3=C;z4=1;z5=0;z6=B;z7=0;z8=1;z9=A;
      a3=C;a6=B;a9=A;
      if(n==0) fout<<x<<'\n';
      else if(n==1) fout<<y<<'\n';
         else if(n==2) fout<<z<<'\n';
         else
         {
            ridicare(n-2);
            fout<<(((x*z3)%m+(y*z6)%m)%m+(z*z9)%m)%m<<'\n';
         }
    }

}