#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
const int MOD=666013;
void multiply2(int a[3][3], int b[3][3])
{
    long long 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]+=1LL*a[i][k]*b[k][j];  //% aici e mai costisitor decat adunarea long long
            }
            c[i][j]%=MOD; //% dureaza > long long
        }
    }
    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            a[i][j]=c[i][j];
        }
    }
}
void multiply(int a[1][3], int b[3][3])
{
    long long c[1][3];
    for (int i=0; i<1; i++) {
        for (int j=0; j<3; j++) {
            c[i][j]=0;
            for (int k=0; k<3; k++) {
                c[i][j]+=1LL*a[i][k]*b[k][j];  //% aici e mai costisitor decat adunarea long long
            }
            c[i][j]%=MOD; //% dureaza > long long
        }
    }
    for (int i=0; i<1; i++) {
        for (int j=0; j<3; j++) {
            a[i][j]=c[i][j];
        }
    }
}
void display_mat(int mat[][3], int n, int m)
{
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            cout<<mat[i][j]<<' ';
        }
        cout<<'\n';
    }
    cout<<'\n';
}
int main()
{
    int t, n;
    fin>>t;
    for (int i=1; i<=t; i++) {
        int iepuri[1][3];
        int m[3][3]={
            {0, 1, 0},
            {0, 0, 1},
            {0, 0, 0}
        };
        fin>>iepuri[0][2]>>iepuri[0][1]>>iepuri[0][0];
        fin>>m[0][0]>>m[1][0]>>m[2][0];
        //display_mat(m, 3, 3);
        //display_mat(iepuri, 1, 3);
        fin>>n;
        /*
        for (int i=1; i<=n; i++) {
            multiply(iepuri, m);
            display_mat(iepuri, 1, 3);
        }
        */
        while (n) {
            if (n%2==1) {
                multiply(iepuri, m);
                //display_mat(iepuri, 1, 3);
                //display_mat(m, 3, 3);
            }
            multiply2(m, m);
            n/=2;
        }
        fout<<iepuri[0][2]<<'\n';
        //cout<<"----------------------"<<endl;
    }
    return 0;
}
/*

*/