#include <iostream>
#include <fstream>

using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
int v[10],u[105],i,j,k,A,B,C,X,Y,Z,n,T,z1,z2,z3,aux;
int main()
{
    in>>T;
    for(k=1;k<=T;k++)
    {
        for(i=1;i<=7;i++) {
                in>>v[i];

        }
     /*       X=v[1];
            Y=v[2];
            Z=v[3];
            A=v[4];
            B=v[5];
            C=v[6];*/
            n=v[7];
            while(n-2) {
            aux=v[3];
            v[3]=v[3]*v[4]+v[2]*v[5]+v[6]*v[1];
            v[1]=v[2];
            v[2]=aux;
            n--; }
    out<<v[3]%666013<<'\n';

    }



    return 0;
}