#include <bits/stdc++.h>
#define Mod 666013

using namespace std;

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

int T,m[5][5],p[5][5];
int a,b,c,x,y,z,n;


void Initializare(int r[5][5])
{
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            r[i][j]=0;
}

void Inmultire(int m1[5][5],int m2[5][5])
{
    int i,j,k;
    int mx[5][5];
    long long s;

    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        {
            s=0;
            for(k=0;k<=3;k++)
                s+=(1LL*m1[i][k]*m2[k][j]);
            mx[i][j]=s%Mod;
        }

    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            m1[i][j]=mx[i][j];
}

void Lgput(int n)
{
    int u[5][5];
    Initializare(u);
    u[1][1]=u[2][2]=u[3][3]=1;
    while(n>0)
    {
        if(n%2==1)Inmultire(u,m);
        Inmultire(m,m);
        n/=2;
    }

    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            m[i][j]=u[i][j];
}


int main()
{
    fin>>T;
    while(T--)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        Initializare(m);
        m[2][1]=m[3][2]=1;
        m[1][3]=c;
        m[2][3]=b;
        m[3][3]=a;
        p[1][1]=x;
        p[1][2]=y;
        p[1][3]=z;

        Lgput(n-2);

        Inmultire(p,m);
        fout<<p[1][3]<<"\n";
    }

    fin.close();
    fout.close();
    return 0;
}