#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
long long u[4][4],rez[4][4],aux[4][4];
int t,zile;
long long x,y,z,a,b,c;
void putere(int exp)
{
    rez[1][1]=1;
    rez[2][2]=1;
    rez[3][3]=1;
    rez[1][2]=0;
    rez[1][3]=0;
    rez[2][1]=0;
    rez[2][3]=0;
    rez[3][1]=0;
    rez[3][2]=0;
    u[1][1]=a;
    u[1][2]=b;
    u[1][3]=c;
    u[2][1]=1;
    u[2][2]=0;
    u[2][3]=0;
    u[3][1]=0;
    u[3][2]=1;
    u[3][3]=0;
    while(exp!=0)
    {
        if(exp%2==0)
        {
            exp=exp/2;
            for(int i=1;i<=3;i++)
            {
                for(int j=1;j<=3;j++)
                {
                    for(int k=1;k<=3;k++)
                    {
                        aux[i][j]=(aux[i][j]+(u[i][k]*u[k][j])%MOD)%MOD;
                    }
                }
            }
            for(int i=1;i<=3;i++)
            {
                for(int j=1;j<=3;j++)
                {
                    u[i][j]=aux[i][j];
                    aux[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++)
                    {
                        aux[i][j]=(aux[i][j]+(rez[i][k]*u[k][j])%MOD)%MOD;
                    }
                }
            }
            for(int i=1;i<=3;i++)
            {
                for(int j=1;j<=3;j++)
                {
                    rez[i][j]=aux[i][j];
                    aux[i][j]=0;
                }
            }
        }

    }
}
int main()
{
    in>>t;
    for(int q=1;q<=t;q++)
    {
        in>>x>>y>>z>>a>>b>>c>>zile;
        putere(zile-2);
        out<<((rez[1][1]*z)%MOD+(rez[1][2]*y)%MOD+(rez[1][3]*x)%MOD)%MOD<<"\n";
    }
    return 0;
}