#include <iostream>
#include<fstream>
using namespace std;
#define R 666013
long long i,j,n,m,k,p,v[3],t,T;
struct mt
{
    long long a[3][3];
}x,y,z,I;
mt P(mt a)
{
    for(i=0;i<3;++i)
    {
        for(j=0;j<3;++j)
        {
            x.a[i][j]=0;
            for(k=0;k<3;++k)
            {
                x.a[i][j]+=(a.a[i][k]*a.a[k][j])%R;
            }
            x.a[i][j]%=R;
        }
    }
    return x;
}
mt X(mt a,mt b)
{
    for(i=0;i<3;++i)
    {
        for(j=0;j<3;++j)
        {
            x.a[i][j]=0;
            for(k=0;k<3;++k)
            {
                x.a[i][j]+=(a.a[i][k]*b.a[k][j])%R;
            }
            x.a[i][j]%=R;
        }
    }
    return x;
}
mt E(mt a,long long p)
{
    if(p<1)return I;
    if(p<2)return a;
    if(p%2>0)return X(E(a,p-1),a);
    return P(E(a,p/2));
}
int main()
{
    for(i=0;i<3;++i)for(j=0;j<3;++j)if(i==j)I.a[i][j]=1;else I.a[i][j]=0;
    ifstream f("iepuri.in");
    f>>T;
    ofstream g("iepuri.out");
    for(t=0;t<T;++t)
    {
        //cout<<t<<'\n';
        f>>v[0]>>v[1]>>v[2];
        for(i=0;i<3;++i)f>>x.a[0][i];
        for(i=1;i<3;++i)
        {
            for(j=0;j<3;++j)x.a[i][j]=0;
            x.a[i][i-1]=1;
        }
        f>>p;y=E(x,p-2);
        if(p<3)g<<v[i]<<'\n';
        else
        {
            k=(v[2]*y.a[0][0] + v[1]*y.a[0][1] + v[0]*y.a[0][2])%R;
            g<<k<<'\n';
        }
    }
    f.close();
    g.close();
    return 0;
}