#include <iostream>
#include<fstream>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
long long x,y,z1,a,b,c,n,z[5],m[5],p,nr,j;
long long mod(long long q)
{
    q%=666013;
    return q;
}
int main()
{
    f>>nr;
    for(j=1;j<=nr;j++)
    {
        f>>x>>y>>z1>>a>>b>>c>>n;
    z[1]=c;z[2]=b;z[3]=a;
    m[1]=x;m[2]=y;m[3]=z1;
    n=mod(n);
    p=n-2;
    while(p)
    {
        a=mod(z[1]*m[1]+z[2]*m[2]+z[3]*m[3]);
        m[1]=mod(m[2]);
        m[2]=mod(m[3]);
        m[3]=a;
        p--;
    }
    g<<a;
    if(j<nr) g<<'\n';
    }

}