#include <fstream>
#define mod 666013

using namespace std;

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

long long x,y,z,a,b,c,n,a1[5][5],a2[5][5],a3[5][5],a4[5][5];

void inmultire(long long a[5][5],long long b[5][5],long long c[5][5])
{
    c[1][1]=((a[1][1]*b[1][1])%mod+(a[1][2]*b[2][1])%mod+(a[1][3]*b[3][1])%mod)%mod;
    c[1][2]=((a[1][1]*b[1][2])%mod+(a[1][2]*b[2][2])%mod+(a[1][3]*b[3][2])%mod)%mod;
    c[1][3]=((a[1][1]*b[1][3])%mod+(a[1][2]*b[2][3])%mod+(a[1][3]*b[3][3])%mod)%mod;
    c[2][1]=((a[2][1]*b[1][1])%mod+(a[2][2]*b[2][1])%mod+(a[2][3]*b[3][1])%mod)%mod;
    c[2][2]=((a[2][1]*b[1][2])%mod+(a[2][2]*b[2][2])%mod+(a[2][3]*b[3][2])%mod)%mod;
    c[2][3]=((a[2][1]*b[1][3])%mod+(a[2][2]*b[2][3])%mod+(a[2][3]*b[3][3])%mod)%mod;
    c[3][1]=((a[3][1]*b[1][1])%mod+(a[3][2]*b[2][1])%mod+(a[3][3]*b[3][1])%mod)%mod;
    c[3][2]=((a[3][1]*b[1][2])%mod+(a[3][2]*b[2][2])%mod+(a[3][3]*b[3][2])%mod)%mod;
    c[3][3]=((a[3][1]*b[1][3])%mod+(a[3][2]*b[2][3])%mod+(a[3][3]*b[3][3])%mod)%mod;
}

void copiere(long long a[5][5],long long b[5][5])
{
    a[1][1]=b[1][1];
    a[1][2]=b[1][2];
    a[1][3]=b[1][3];
    a[2][1]=b[2][1];
    a[2][2]=b[2][2];
    a[2][3]=b[2][3];
    a[3][1]=b[3][1];
    a[3][2]=b[3][2];
    a[3][3]=b[3][3];
}

void putere(long long p)
{
    if(p>1)
    {
        if(p%2==1)
        {
            putere(p-1);
            inmultire(a1,a2,a3);
            copiere(a1,a3);
        }
        else
        {
            putere(p/2);
            inmultire(a1,a1,a3);
            copiere(a1,a3);
        }
    }
}

void citire()
{
    fin>>x>>y>>z>>a>>b>>c>>n;
    a1[1][2]=a1[2][3]=1;
    a1[1][1]=a;
    a1[2][1]=b;
    a1[3][1]=c;
    a1[1][3]=a1[2][2]=a1[3][2]=a1[3][3]=0;
    copiere(a2,a1);

}

void afisare()
{
    a4[1][1]=z;
    a4[1][2]=y;
    a4[1][3]=x;
    a4[2][1]=a4[2][2]=a4[2][3]=a4[3][1]=a4[3][2]=a4[3][3]=0;
    inmultire(a4,a1,a3);
    fout<<a3[1][1]%mod<<"\n";
}

int main()
{
    long long t;
    fin>>t;
    for(long long i=1;i<=t;i++)
    {
        citire();
        putere(n-2);
        afisare();
    }
    return 0;
}