#include <iostream>
#include <fstream>
//#include <stdio>
//#include <time>
//#include <dos>
//#include <windows>
using namespace std;
int main()
{
 
long int x,y,z,a,b,c,n,s1,s2,s3,s;
int i,j,t;
 ifstream f("iepuri.in");
 ofstream g("iepuri.out");
//long int before = GetTickCount();
  f>>t;
 cout<<t;
  for (j=1; j<=t; j++)
{
 f>>x>>y>>z>>a>>b>>c>>n;


 s1=x;
 s2=y;
 s3=z;
 for (i=1; i<=n-2; i++)
 { 
  s=a*s3+b*s2+c*s1;
    if(s>666013)
	s=s%666013;
  s1=s2;
  s2=s3;
  s3=s;


 }
 g<<s%666013<<endl;
  }
//long int after = GetTickCount();
 
 f.close();
 g.close();
 //cout<<"time="<<after-before<<endl;;

 system("pause");
return 0;
}