#include <iostream>
#include <fstream>

using namespace std;

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

int M[3][3], A[3][3], r[3][3];
const int MOD=666013;

void inm(int a[3][3], int b[3][3], int c[3][3])
{
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            c[i][j]=0;
            for(int k=0;k<3;k++)
                c[i][j]+=(a[i][k]*b[k][j])%MOD;
        }
    }
}

void exp(int b[3][3], int p)
{
    r[0][0]=1;
    r[1][1]=1;
    r[2][2]=1;
    for(int bit=0;(1<<bit)<=p;bit++)
    {
        int aux[3][3];
        if(p&(1<<bit))
        {
            inm(r,b,aux);
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    r[i][j]=aux[i][j];
        }
        inm(b,b,aux);
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                b[i][j]=aux[i][j];
    }
}

int main()
{
    int t;
    fin>>t;
    for(int i=1;i<=t;i++)
    {
        int x, y, z, a, b, c, n;
        fin>>x>>y>>z>>a>>b>>c>>n;
        M[0][0]=a;
        M[1][0]=b;
        M[2][0]=c;
        M[0][1]=1;
        M[1][2]=1;
        A[0][0]=z;
        A[0][1]=y;
        A[0][2]=x;
        exp(M,n-2);
        int R[3][3];
        inm(A,r,R);
        fout<<R[0][0]<<'\n';
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                r[i][j]=0;
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                M[i][j]=0;
    }
    return 0;
}