#include <fstream>

using namespace std;

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

#define MOD 666013

int a,b,n,x,y,z,c,teste;

struct matrice
{
    int n,m,a[10][10];
};

matrice mat,init;

void afis (matrice a)
{
    for (int i=1; i<=a.n; i++)
    {
        for (int j=1; j<=a.m; j++)
        {
            fout<<a.a[i][j]<<' ';
        }
        fout<<'\n';
    }
}

matrice inmultire (matrice a, matrice b)
{
    matrice aux;
    int i,j,n=a.n,m=b.m,k,com=a.m;
    aux.n=n,aux.m=m;
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=m; j++)
        {
            aux.a[i][j]=0;
            for (k=1; k<=com; k++)
            {
                aux.a[i][j]+=a.a[i][k]*b.a[k][j];
                aux.a[i][j]%=MOD;
            }
        }
    }
    return aux;
}

matrice exp_rapida (matrice a, int n)
{
    if (n==1)
    {
        return a;
    }
    matrice aux=exp_rapida (a,n/2);
    if (n%2==0)
    {
        return inmultire(aux,aux);
    }
    else
    {
        return inmultire(inmultire(aux,aux),a);
    }
}

signed main()
{
    fin>>teste;
    while (teste--)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        mat.n=1;
        mat.m=3;
        mat.a[1][1]=z;
        mat.a[1][2]=y;
        mat.a[1][3]=x;
        init.n=init.m=3;
        init.a[1][1]=a;
        init.a[2][1]=b;
        init.a[3][1]=c;
        init.a[1][2]=init.a[2][3]=1;
        matrice answer=inmultire(mat,exp_rapida(init,n-2));
        fout<<answer.a[1][1]<<'\n';
    }
    return 0;
}