#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD=666013;

void inmultire(int a[3][3], int b[3][3])
{//a=a*b
    int c[3][3];
    int i, j, k;
    for(i=0; i<=2; i++)for(j=0; j<=2; j++)
    {
        c[i][j]=0;
        for(k=0; k<=2; k++) c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
    }
    for(i=0; i<=2; i++) for(j=0; j<=2; j++) a[i][j]=c[i][j];
}
void putere(int sol[3][3], int mx[3][3], int k)
{
    while(k)
    {
        if(k%2==1) {inmultire(sol, mx); k--;}
        else {inmultire(mx, mx); k=k/2;}
    }
}
int ox[3][3], mx[3][3], sol[3][3];
int main()
{
    int ct, teste;
    fin>>teste;

    int x, y, z, a, b, c, n, i, j;
    for(ct=1; ct<=teste; ct++)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        //construiesc ox
        for(i=0; i<=2; i++) for(j=0; j<=2; j++) ox[i][j]=0;
        ox[0][0]=x; ox[0][1]=y; ox[0][2]=z;

        //construiesc mx
        for(i=0; i<=2; i++) for(j=0; j<=2; j++) mx[i][j]=0;
        mx[0][2]=c; mx[1][2]=b; mx[2][2]=a;
        mx[1][0]=1; mx[2][1]=1;

        //construiesc sol = matricea unitate
        for(i=0; i<=2; i++) for(j=0; j<=2; j++) sol[i][j]=0;
        sol[0][0]=1; sol[1][1]=1; sol[2][2]=1;

        //calculez ox * (mx^n)
        putere(sol, mx, n);
        inmultire(ox, sol);

        //afisez ox[0][0];
        fout<<ox[0][0]<<"\n";
    }
    return 0;
}