#include <fstream>
# define MOD 666013
using namespace std;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
long long U[4][4],rez[4][4];
void ridicare(long long I[4][4], long long exp)
{

    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(i==j)
                U[i][j]=1;
            else
                U[i][j]=0;
    while(exp!=0)
    {
        if(exp%2==0)
        {
            exp/=2;
            for(int i=1;i<=3;i++)
                for(int j=1;j<=3;j++)
                    for(int k=1;k<=3;k++)
                        rez[i][j]=(rez[i][j]+I[i][k]*I[k][j])%MOD;
            for(int i=1;i<=3;i++)
                for(int j=1;j<=3;j++)
                {
                    I[i][j]=rez[i][j];
                    rez[i][j]=0;
                }
        }
        else
        {
            exp--;
            for(int i=1;i<=3;i++)
                for(int j=1;j<=3;j++)
                    for(int k=1;k<=3;k++)
                        rez[i][j]=(rez[i][j]+U[i][k]*I[k][j])%MOD;
             for(int i=1;i<=3;i++)
                for(int j=1;j<=3;j++)
                {
                    U[i][j]=rez[i][j];
                    rez[i][j]=0;
                }
        }
    }
}

int main()
{
    long long nrt,k,n,T[4][4],I[4][4];
    cin>>nrt;
    for(k=1;k<=nrt;k++)
    {
        cin>>T[1][1]>>T[2][1]>>T[3][1];
        I[1][1]=I[1][3]=I[2][1]=I[2][2]=0;
        I[1][2]=I[2][3]=1;
        cin>>I[3][3]>>I[3][2]>>I[3][1]>>n;
        ridicare(I,n-2);
        cout<<((U[3][1]*T[1][1])%MOD + (U[3][2]*T[2][1])%MOD +(U[3][3]*T[3][1])%MOD)%MOD<<"\n";
    }
    return 0;
}