#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 * 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;
}