#include <stdio.h>
#include <fstream>
#include <set>
using namespace std;

#define in "iepuri.in"
#define out "iepuri.out"
#define modulo 666013

int T, X, Y, Z, A_, B_, C_;
int S[4];
long long N;

typedef int Matr[11][11];
set<int> L;

Matr A, M, C, D;

void Inmultire(Matr A, Matr B)
{
    for ( int i = 1; i <= 3; i++ )
        for ( int j = 1; j <= 3; j++ )
            C[i][j] = 0;
        
    for ( int i = 1; i <= 3; i++ )
        for ( int j = 1; j <= 3; j++ )
        {
            for ( int k = 1; k <= 3; k++ )
            {
                C[i][j] = ( C[i][j] + ( A[k][j]*B[i][k] )%modulo ) % modulo;
            }
        }
    
    for ( int i = 1; i <= 3; i++ )
        for ( int j = 1; j <= 3; j++ )
            M[i][j] = C[i][j];
}

int Putere(int P)
{
    while ( P > 1 )
    {
          L.insert(P);
          if ( P % 2 == 0 ) P /= 2;
          else              P -= 1, P /= 2;
    }
    L.insert(2);
}

int Solve();


int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &T);
    for ( int i = 0; i < T; i++ )
    {
        int Q = 0;
        scanf("%d%d%d%d%d%d%d", &S[1], &S[2], &S[3], &A_, &B_, &C_, &N);
        if ( N < 4 ) printf("%d", S[N] );
        else
        {
            A[1][1] = 0; A[1][2] = 1; A[1][3] = 0;
            A[2][1] = 0; A[2][2] = 0; A[2][3] = 1;
            A[3][1] = C_; A[3][2] = B_; A[3][3] = A_;
            
            int q = Solve();
            printf("%d\n", q );
        }
    }
}

int Solve()
{
    for ( int i = 1; i <= 3; i++ )
        for ( int j = 1; j <= 3; j++ )
            M[i][j] = 0;
            
    Putere(N);
    
    set<int>::iterator it = L.begin();
    int last=2;
    it++;
    
    Inmultire(A,A);
    
    for ( ; it != L.end(); it++ )
    {
        if ( *it % 2 == 0 ) Inmultire(M,M);
        else
        {
            if ( *it - last > 2 ) Inmultire(M,M);
            Inmultire(A,M);
        }
        last = *it;
    }
    L.clear();
    int Val = 0;
    
    for ( int i = 1; i <= 3; i++ )
    {
        Val = ( Val + ( M[1][i]*S[i])%modulo ) % modulo;
    }
    
    //Val %= modulo;
    return Val;
}