#include <iostream>
#include <fstream>
using namespace std;
int X,Y,Z,A,B,C,T,N,n;
void iepuri(int &nr)
{
    nr=A*Z+B*Y+C*X;
}
int main()
{
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    f>>T;
    while (T!=0)
    {
        f>>X>>Y>>Z>>A>>B>>C>>N;
        T--;
        while (N!=2)
        {
            iepuri(n);
            X=Y;
            Y=Z;
            Z=n;
            N--;
        }
        g<<Z%666013<<endl;
    }
}