#include <iostream>
#include <fstream>
#define NMAX 4
#define MOD 666013
using namespace std;

int M[NMAX][NMAX],AUX[NMAX][NMAX],I[1][NMAX],REZ[NMAX][NMAX];
int n,x,y,z,a,b,c,t;

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

void multiplica(int a[][NMAX],int b[][NMAX], int aux[][NMAX],int linie, int coloana)
{
    for(int i=0;i<linie;i++) {
        for(int j=0;j<coloana;j++) {
            for(int k=0;k<coloana;k++) {
                aux[i][j] = (aux[i][j] + 1LL*a[i][k] * b[k][j])%MOD;
            }
        }
    }
}

void reset(int a[][NMAX], int l, int c)
{
    for(int i=0;i<l;i++) {
        for(int j=0;j<c;j++) {
            a[i][j] = 0;
        }
    }
}

void copiaza(int rez[][NMAX],int aux[][NMAX])
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            rez[i][j] = aux[i][j];

        }
    }
}

void afisare(int a[][NMAX],int l,int c)
{
    for(int i=0;i<l;i++)
    {
        for(int j=0;j<c;j++)
        {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl << endl << endl;
}

void ridicareLg()
{

    while(n>0)
    {
        if(n%2==1)
        {
            multiplica(REZ,M,AUX,3,3);
            //afisare(AUX);
            copiaza(REZ, AUX);
            reset(AUX,3,3);
            n--;
            //afisare(REZ);
        }
        n=n/2;

        multiplica(M,M,AUX,3,3);
        copiaza(M,AUX);
        reset(AUX,3,3);
    }
}

void init()
{
    I[0][0] = a;I[0][1] = b;I[0][2] = c;

    M[0][0] = 0;M[0][1] = 0;M[0][2] = z;
    M[1][0] = 1;M[1][1] = 0;M[1][2] = y;
    M[2][0] = 0;M[2][1] = 1;M[2][2] = x;

    REZ[0][0] = 1;REZ[0][1] = 0;REZ[0][2] = 0;
    REZ[1][0] = 0;REZ[1][1] = 1;REZ[1][2] = 0;
    REZ[2][0] = 0;REZ[2][1] = 0;REZ[2][2] = 1;

}

int main()
{
    in >> t;

    for(int i=0;i<t;i++)
    {
        in >> a >> b >> c;
        in >> x >> y >> z;
        in >> n;
        init();
        n = n-2;
        ridicareLg();
        multiplica(I,REZ,AUX,1,3);
        //afisare(REZ,3,3);
        out <<  AUX[0][2]%MOD << "\n";
        reset(AUX,3,3);
    }
    return 0;
}