#include <cstdio>
#include <iostream>
using namespace std;

FILE * in = fopen("iepuri.in","r");
FILE * out = fopen("iepuri.out","w");

struct Matrice {
    int m[3][3];
    Matrice() {
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                m[i][j] = 0;
            }
        }
    }

    Matrice & operator * (const Matrice &altaMatrice) {
        static Matrice raspuns;
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                long long aux = 0;
                for(int k=0; k<3; k++) {
                        aux += (1LL * this->m[i][k] * altaMatrice.m[k][j]);
                        if(aux>666013)
                            aux %= 666013;
                }
                raspuns.m[i][j] = aux;
            }
        }
        return raspuns;
    }

    void print() {
        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {
                cout<<m[i][j]<<' ';
            }
            cout<<'\n';
        }
        cout<<'\n';
    }

    void init(int a,int b,int c)
    {
    this->m[0][0]=0; this->m[0][1]=0; this->m[0][2]=c;
    this->m[1][0]=1; this->m[1][1]=0; this->m[1][2]=b;
    this->m[2][0]=0; this->m[2][1]=1; this->m[2][2]=a;
    }

    void neutru()
    {
        this->m[0][0]=1; this->m[0][1]=0; this->m[0][2]=0;
        this->m[1][0]=0; this->m[1][1]=1; this->m[1][2]=0;
        this->m[2][0]=0; this->m[2][1]=0; this->m[2][2]=1;
    }
};
void put(Matrice &m,int exp)
{
    Matrice  rez;
    rez.neutru();
    for(int d=0; (1<<d) <= exp; d++)
    {
        if((1<<d)&exp)
            rez = rez*m;
        m = m*m;
    }
    m=rez;
}
int teste;

int main() {
    fscanf(in,"%d",&teste);
    while(teste--)
    {
        int a,b,c,x,y,z,n;
        fscanf(in,"%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        Matrice mat;
        mat.init(a,b,c);

        put(mat,n-2);
        Matrice r;
        r.m[0][0]=x; r.m[0][1]=y; r.m[0][2]=z;
        r = r*mat;
        fprintf(out,"%d\n",r.m[0][2]%666013);
    }
    return 0;
}