#include <iostream>
#include <fstream>

using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");


int main()
{
    long int r=666013, x, y, z, a, b, c, n, i, nz, nzc, s;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x>>y>>z>>a>>b>>c>>nz;
        nzc=2;
        while(nzc!=nz)
        {
            nzc++;
            s=z;
            z=z*a+y*b+x*c;
            x=y;
            y=s;
        }
        g<<z%r<<endl;
    }
    return 0;
}