#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const int MOD = 666013;

int Q;
long long x,y,z,A,B,C,n;
long long T;
long long mat[5];
long long I[5][5];
long long I1[5][5];
long long a[5][5];
void Inmultire()
{
    for(int i=1; i<=4; ++i)
        for(int j=1; j<=4; ++j)
        {
            long long val=0;
            for(int x=1; x<=4; ++x)
                val=1LL*(val+a[x][j]*a[i][x])%MOD;
            I[i][j]=val;
        }
}
void Inmultire1()
{
    for(int i=1; i<=4; ++i)
        for(int j=1; j<=4; ++j)
        {
            long long val=0;
            for(int x=1; x<=4; ++x)
                val=1LL*(val+a[x][j]*I1[i][x])%MOD;
            I[i][j]=val;
        }
}
void cpy()
{
    for(int i=1;i<=4;++i)
        for(int j=1;j<=4;++j)
        a[i][j]=I[i][j];
}
void Exp( long long p)
{
    if(p==1)return ;
    if(p%2==1)
    {
        Exp(p-1);
        cpy();
        Inmultire1();

    }
    else
    {
        Exp(p/2);
        cpy();
        Inmultire();

    }
}
void Iepuri()
{
    for(int i=1;i<=4;++i)
        for(int j=1;j<=4;++j)
        I[i][j]=I1[i][j]=0;
    T=1LL*(x*A+y*B+z*C)%MOD;
    if(n==3)
    {
        fout<<T<<"\n";
        return ;
    }
    mat[1]=x;
    mat[2]=y;
    mat[3]=z;
    mat[4]=T;
    I[2][1]=I1[2][1]=1;
    I[3][2]=I1[3][2]=1;
    I[4][3]=I1[4][3]=1;
    I[2][4]=I1[2][4]=A;
    I[3][4]=I1[3][4]=B;
    I[4][4]=I1[4][4]=C;

    Exp(n-3);

    long long val=0;

    for(int i=1;i<=4;++i)
    val=(val+1LL*mat[i]*I[i][4])%MOD;


    fout<<val<<"\n";
}
void Do()
{
    for(int q=1; q<=Q; ++q)
    {
        fin>>x>>y>>z>>C>>B>>A>>n;
        Iepuri();
    }
}
int main()
{
    fin>>Q;
    Do();
    return 0;
}