#include <fstream>
#include <stdlib.h>
using namespace std;

long long m[4][4],mat[4][4];
const int mod=666013;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

void inmultire(long long mat1[][4],long long mat2[][4])
{
    int i,j,k,aux[4][4]={};
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            for(k=1;k<=3;k++)
                aux[i][j]+=mat1[i][k]*mat2[k][j];
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            mat[i][j]=aux[i][j]%mod;
}

void putere(long long p)
{
    if(p==1)
    {
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                mat[i][j]=m[i][j];
        return ;
    }
    if(p%2==0)
    {
        putere(p/2);
        inmultire(mat,mat);
    }
    else
    {
        putere(p-1);
        inmultire(m,mat);

    }
}

int main()
{
    long long n,t,i,x,y,z,a,b,c;
    cin>>t;
    m[1][2]=1;
    m[2][3]=1;
    for(i=1;i<=t;i++)
    {
        cin>>x>>y>>z>>a>>b>>c>>n;
        m[1][1]=a;
        m[2][1]=b;
        m[3][1]=c;
        putere(n-2);
        cout<<(z*mat[1][1]+y*mat[2][1]+x*mat[3][1])%mod<<'\n';
    }
    return 0;
}