#include <fstream>
#define mod 666013

using namespace std;
ifstream fin ("iepuri.in");
ofstream fout("iepuri.out");
int n[5][5], m[5][5], s[5][5];
int t,ok,k,a,b,c,x,y,z;

void atrib(int m[5][5], int n[5][5])
{
    int i; int j;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            m[i][j]=n[i][j];
}

void calc(int a[5][5], int b[5][5])
{
    int i,j,l;
    long long aux[5][5];
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        {
            aux[i][j]=0;
            for(l=1;l<=3;l++)
                aux[i][j]=(aux[i][j]+(1LL*a[i][l]*b[l][j])%mod)%mod;
            aux[i][j]%=mod;
        }
     for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            a[i][j]=aux[i][j];
}

void reset()
{
    ok=0;
    n[1][1]=a;n[1][2]=b;n[1][3]=c;
    n[2][1]=1;n[2][2]=0;n[2][3]=0;
    n[3][1]=0;n[3][2]=1;n[3][3]=0;
    m[1][1]=0;m[1][2]=0;m[1][3]=0;
    m[2][1]=0;m[2][2]=0;m[2][3]=0;
    m[3][1]=0;m[3][2]=0;m[3][3]=0;
}

int sol()
{
    long long aux=0;
    aux+=(1LL*m[1][1]*z)%mod;
    aux+=(1LL*m[1][2]*y)%mod;
    aux+=(1LL*m[1][3]*x)%mod;
    return aux%mod;
}

int main()
{
    fin>>t;
    for(;t>0;t--)
    {
        fin>>x>>y>>z>>a>>b>>c>>k;
        k-=2;
        reset();
        while(k>1)
        {
            if(k%2==0)
            {
                calc(n, n);
                k/=2;
            }
            else
                if(k%2==1)
                {
                    if(ok==1)
                        calc(m, n);
                    else
                    {
                        atrib(m, n);
                        ok=1;
                    }
                    calc(n, n);
                    k/=2;
                }
        }
        if(ok==1)
            calc(m, n);
        else
        {
            atrib(m, n);
            ok=1;
        }
        if(k==2)
            fout<<(x+y+z)%mod;
        else
            fout<<sol();
        fout<<"\n";
    }
    fin.close();
    fout.close();
    return 0;
}