#include <fstream>
#include <cstring>
#define DMAX 5
#define MOD 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");

int k, Z[DMAX][DMAX], D=3,a,b,c,X,Y,W;
long long n;

void multiplication(int A[DMAX][DMAX], int B[DMAX][DMAX], int C[DMAX][DMAX])
{
    int aux[DMAX][DMAX];
    //initializare cu 0 aux
    memset(aux, 0, sizeof(aux));
    for (int i=1; i<=D; i++)
        for (int j=1; j<=D;j++)
            for(int k=1; k<=D; k++)
                aux[i][j]= (aux[i][j] + 1LL*A[i][k]*B[k][j]) % MOD;
    memcpy(C, aux, sizeof(aux));
}

void exponentiere(int Z[DMAX][DMAX], int K)
{
    int M[DMAX][DMAX];
    memset(M, 0, sizeof(M));
    M[1][1]=W;M[1][2]=Y;M[1][3]=X;
    while (K!=1)
        if (K % 2==0)
        {
            multiplication(Z,Z,Z);
            K/=2;
        }
        else
        {
            multiplication(M, Z, M);
            K--;
        }
    multiplication(M,Z,Z);
}

int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>X>>Y>>W>>a>>b>>c>>k;
        Z[1][1]=a; Z[1][2]=1; Z[1][3]=0;
        Z[2][1]=b; Z[2][2]=0; Z[2][3]=1;
        Z[3][1]=c; Z[3][2]=0; Z[3][3]=0;
        exponentiere(Z, k-2);
        g<<Z[1][1]<<'\n';
    }
    f.close();g.close();
    return 0;
}