#include <fstream>
using namespace std;

#define infile "iepuri.in"
#define outfile "iepuri.out"

#define MOD 666013

using namespace std;

class Matrix {
    public :

    int **matrix;
    int n, m;

    Matrix(int lines, int columns){
        n = lines;
        m = columns;

        matrix = new int*[n];

        for(int i=0; i<n; ++i){
           matrix[i] = new int[m];
           for(int j=0; j<m; ++j)
               matrix[i][j] = 0;
        }
    }

    Matrix :: Matrix operator * (Matrix &that){
        int p = that.m;

        Matrix res = *new Matrix(n, p);

        for(int i=0; i<n; ++i)
            for(int j=0; j<p; ++j)
                for(int k=0; k<m; ++k)
                   res.matrix[i][j] = (1LL * res.matrix[i][j] + (1LL * matrix[i][k] * that.matrix[k][j])) % MOD;

        return res;
    }
};


int T;


Matrix powlog(Matrix N, int P){
    if(P == 1)
       return N;

    Matrix res = powlog(N,P/2);
    res = res * res;

    if(P&1)
      res = res * N;

    return res;
}


int main(){
    ifstream fin(infile);
    ofstream fout(outfile);

    for(fin >> T; T; --T){
        int N;
        Matrix M1 = *new Matrix(3,3);
        Matrix M2 = *new Matrix(3,1);

        for(int i=2; i>=0; --i)
           fin >> M2.matrix[i][0];

        for(int i=0; i<3; ++i)
            for(int j=0; j<3; ++j)
               if(!i)
                  fin >> M1.matrix[i][j];
               else
                  M1.matrix[i][j] = (i==1 && j==0) || (i==2 && j==1);

        fin >> N;

        fout << (powlog(M1, N-2) * M2).matrix[0][0] << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}