#include <iostream>
#include <fstream>
#include <vector>
#define modulo 666013
#define nmax 200000000

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int w[nmax];
int T,x,y,z,a,b,c,N,rez;
int answer(int N)
{
    for(int j = 3; j <= N; j++)
    {
        w[j]=a*z+b*y+c*x;
      x=y;
      y=z;
      z=w[j];
    }
    return w[N];
}
int main()
{

      fin>>T;
     while(T--)
     {
        int u=0;
         fin>>x>>y>>z>>a>>b>>c>>N;
       w[u++]=x;
       w[u++]=y;
       w[u++]=z;
         rez=answer(N);
         fout<<rez%666013<<'\n';
     }


    return 0;
}