#include <fstream>
#include <string>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

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

#define n_max
#define INF 1 << 30
#define MOD 666013

#define ll long long
#define ull unsigned long long

#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define FOR(g) \
    for(vector<int>::iterator it=g.begin(); it!=g.end(); ++it)
#define nxt (*it)

#define min(x,y) x<y ? x : y
#define max(x,y) x>y ? x : y
using namespace std;

class Matrix {
    public :

    int matrix[3][3];
    int n, m;

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

       // matrix = new int*[lines];

        for(int i=0; i<=n; ++i){
          // matrix[i] = new int[columns];

           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+1, p+1);

        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 = N* res;

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