#include <iostream>
#include <fstream>
using namespace std;

int main()
{
   long long int n,i,z1,s,z2,z3,zm1,zm2,zm3,zum,nn;
ifstream f ("iepuri.in");
ofstream g ("iepuri.out");
   f>>n;

   for(i=1;i<=n;i++)
   { f>>z1>>z2>>z3>>zm1>>zm2>>zm3>>nn;
   nn=nn-2;
       while(nn>0)
       {zum=zm3*z1+zm2*z2+zm1*z3;
        z1=z2;
        z2=z3;
        z3=zum;
        s+=zum;
         nn--;

       }
    g<<zum%666013<<'\n';

   }


}