#include <fstream>

using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
int mat[4][2], baza[4][4], rez[4][4], m;
void putere(int baza[][4], int exp)
{
    int aux[4][4], i, j, k;
    while(exp>0)
    {
        for(i=1;i<=3;i++)
			for(j=1;j<=3;j++)
				aux[i][j]=0;

        if(exp%2==0)
        {
            exp/=2;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    for(k=1;k<=3;k++)
                        aux[i][j]+=1LL*(baza[i][k]*baza[k][j])%m;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                        baza[i][j]=aux[i][j];
        }
        else
        {
            exp--;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    for(k=1;k<=3;k++)
                         aux[i][j]+=1LL*(baza[i][k]*rez[k][j])%m;
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                        rez[i][j]=aux[i][j];
        }
    }
}
int main()
{
    int n, i, nr, rezi, p, j, k, x, y, z;
    m=666013;
    cin>>nr;
    for(k=1;k<=nr;k++)
    {
        for(i=1;i<=3;i++)
            for(j=1;j<=3;j++)
                baza[i][j]=0;
        baza[1][2]=1; baza[2][3]=1;
        cin>>x>>y>>z>>baza[3][3]>>baza[3][2]>>baza[3][1]>>n;
        rez[1][2]=rez[1][3]=rez[2][1]=rez[2][3]=rez[3][1]=rez[3][2]=0;
		rez[1][1]=rez[2][2]=rez[3][3]=1;
        putere(baza, n-2);
        rezi=((x*rez[3][1]*1LL)%m+(y*rez[3][2]*1LL)%m+(z*rez[3][3]*1LL)%m)%m;
        cout<<rezi<<'\n';

    }
    return 0;
}