#include <fstream>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
unsigned long long x,y,z,a,b,c,n,t;
unsigned long long m[3][3],M[3][3],aux[3][3],aux1[3][3];
#define MOD 666013


void afis()
{
    int ii,jj;
    for(ii=0;ii<3;ii++)
    {
        for(jj=0;jj<3;jj++) g<<M[ii][jj]<<' ';
        g<<'\n';
    }
    g<<'\n'<<'\n';
}

void inm(unsigned long long a[3][3],unsigned long long b[3][3], unsigned long long c[3][3])
{
    unsigned long long d[3][3];
    d[0][0]=((1LL*a[0][0]*b[0][0])%MOD+(1LL*a[0][1]*b[1][0])%MOD +(1LL*a[0][2]*b[2][0])%MOD)%MOD;
    d[0][1]=((1LL*a[0][0]*b[0][1])%MOD+(1LL*a[0][1]*b[1][1])%MOD +(1LL*a[0][2]*b[2][1])%MOD)%MOD;
    d[0][2]=((1LL*a[0][0]*b[0][2])%MOD+(1LL*a[0][1]*b[1][2])%MOD +(1LL*a[0][2]*b[2][2])%MOD)%MOD;
    d[1][0]=((1LL*a[1][0]*b[0][0])%MOD+(1LL*a[1][1]*b[1][0])%MOD +(1LL*a[1][2]*b[2][0])%MOD)%MOD;
    d[1][1]=((1LL*a[1][0]*b[0][1])%MOD+(1LL*a[1][1]*b[1][1])%MOD +(1LL*a[1][2]*b[2][1])%MOD)%MOD;
    d[1][2]=((1LL*a[1][0]*b[0][2])%MOD+(1LL*a[1][1]*b[1][2])%MOD +(1LL*a[1][2]*b[2][2])%MOD)%MOD;
    d[2][0]=((1LL*a[2][0]*b[0][0])%MOD+(1LL*a[2][1]*b[1][0])%MOD +(1LL*a[2][2]*b[2][0])%MOD)%MOD;
    d[2][1]=((1LL*a[2][0]*b[0][1])%MOD+(1LL*a[2][1]*b[1][1])%MOD +(1LL*a[2][2]*b[2][1])%MOD)%MOD;
    d[2][2]=((1LL*a[2][0]*b[0][2])%MOD+(1LL*a[2][1]*b[1][2])%MOD +(1LL*a[2][2]*b[2][2])%MOD)%MOD;
    int i,j;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++) c[i][j]=d[i][j];
}

void Alan(unsigned long long a[3][3], unsigned long long b[3][3], int n)
{
    if(n==0)
    {
        int ii,jj;
        for(ii=0;ii<3;ii++)
            for(jj=0;jj<3;jj++)
                b[ii][jj]=0;
        b[0][0]=b[1][1]=b[2][2]=1;
    }
    else if(n==1)
    {
        int ii,jj;
        for(ii=0;ii<3;ii++)
            for(jj=0;jj<3;jj++)
                b[ii][jj]=a[ii][jj];
    }
        else{
            unsigned long long c[3][3];
            Alan(a,c,n/2);
            if(n%2==0) inm(c,c,b);
            else {
                inm(c,c,b);
                inm(b,a,b);
            }
        }
}

void zero()
{
    int ii,jj;
        for(ii=0;ii<3;ii++)
            for(jj=0;jj<3;jj++)
                m[ii][jj]=M[ii][jj]=aux[ii][jj]=aux1[ii][jj]=0;
}


int main()
{
    f>>t;
    for(int ind=1;ind<=t;ind++)
    {
        zero();
        f>>x>>y>>z>>a>>b>>c>>n;
        m[0][0]=m[0][1]=m[1][1]=m[2][0]=0;
        m[1][0]=m[2][1]=1;
        m[0][2]=c;
        m[1][2]=b;
        m[2][2]=a;
        Alan(m,M,n-2);
        aux[0][0]=x; aux[0][1]=y; aux[0][2]=z;
        inm(aux,M, aux1);
        g<<aux1[0][2]%MOD<<'\n';
    }
    f.close();
    g.close();
    return 0;
}