#include <iostream>
#include <fstream>
using namespace std;
#define ull unsigned long long int
#define m 666013
ifstream in("iepuri.in");
ofstream out("iepuri.out");
struct matrice{
ull a,b,c,d,e,f,g,h,i;} base,res;
int main()
{
    ull k,z1,z2,z3,t,o;
    in>>t;
    for(o=1;o<=t;o++)
    {

    in>>z1>>z2>>z3>>base.a>>base.b>>base.c>>k;
    res.a=1;
    res.b=0;
    res.c=0;
    res.d=0;
    res.e=1;
    res.f=0;
    res.g=0;
    res.h=0;
    res.i=1;
    base.d=1;
    base.e=0;
    base.f=0;
    base.g=0;
    base.h=1;
    base.i=0;
    k-=2;
    struct matrice s;
    while(k)
    {
        if(k&1)
          {
              s.a = ( ( ((res.a%m)*(base.a%m))%m+((res.b%m)*(base.d%m))%m )%m +((res.c%m)*(base.g%m))%m )%m;
              s.b = ( ( ((res.a%m)*(base.b%m))%m+((res.b%m)*(base.e%m))%m )%m +((res.c%m)*(base.h%m))%m )%m;
              s.c = ( ( ((res.a%m)*(base.c%m))%m+((res.b%m)*(base.f%m))%m )%m +((res.c%m)*(base.i%m))%m )%m;
              s.d = ( ( ((res.d%m)*(base.a%m))%m+((res.e%m)*(base.d%m))%m )%m +((res.f%m)*(base.g%m))%m )%m;
              s.e = ( ( ((res.d%m)*(base.b%m))%m+((res.e%m)*(base.e%m))%m )%m +((res.f%m)*(base.h%m))%m )%m;
              s.f = ( ( ((res.d%m)*(base.c%m))%m+((res.e%m)*(base.f%m))%m )%m +((res.f%m)*(base.i%m))%m )%m;
              s.g = ( ( ((res.g%m)*(base.a%m))%m+((res.h%m)*(base.d%m))%m )%m +((res.i%m)*(base.g%m))%m )%m;
              s.h = ( ( ((res.g%m)*(base.b%m))%m+((res.h%m)*(base.e%m))%m )%m +((res.i%m)*(base.h%m))%m )%m;
              s.i = ( ( ((res.g%m)*(base.c%m))%m+((res.h%m)*(base.f%m))%m )%m +((res.i%m)*(base.i%m))%m )%m;
              res = s;
              //cout<<res.a<<" "<<res.b<<" "<<res.c<<"\n"<<res.d<<" "<<res.e<<" "<<res.f<<"\n"<<res.g<<" "<<res.h<<" "<<res.i<<"\n\n";
          }
        s.a = (( ((base.a%m)*(base.a%m))%m+((base.b%m)*(base.d%m))%m )%m +((base.c%m)*(base.g%m))%m )%m;
        s.b = (( ((base.a%m)*(base.b%m))%m+((base.b%m)*(base.e%m))%m )%m +((base.c%m)*(base.h%m))%m )%m;
        s.c = (( ((base.a%m)*(base.c%m))%m+((base.b%m)*(base.f%m))%m )%m +((base.c%m)*(base.i%m))%m )%m;
        s.d = (( ((base.d%m)*(base.a%m))%m+((base.e%m)*(base.d%m))%m )%m +((base.f%m)*(base.g%m))%m )%m;
        s.e = (( ((base.d%m)*(base.b%m))%m+((base.e%m)*(base.e%m))%m )%m +((base.f%m)*(base.h%m))%m )%m;
        s.f = (( ((base.d%m)*(base.c%m))%m+((base.e%m)*(base.f%m))%m )%m +((base.f%m)*(base.i%m))%m )%m;
        s.g = (( ((base.g%m)*(base.a%m))%m+((base.h%m)*(base.d%m))%m )%m +((base.i%m)*(base.g%m))%m )%m;
        s.h = (( ((base.g%m)*(base.b%m))%m+((base.h%m)*(base.e%m))%m )%m +((base.i%m)*(base.h%m))%m )%m;
        s.i = (( ((base.g%m)*(base.c%m))%m+((base.h%m)*(base.f%m))%m )%m +((base.i%m)*(base.i%m))%m )%m;
        base = s;
        k=k>>1;
     }
      out<<( ( ( ((res.a%m)*(z3%m))%m+((res.b%m)*(z2%m))%m)%m+((res.c%m)*(z1%m))%m)%m)<<"\n";
    }
}