#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

ifstream fin  ("iepuri.in");
ofstream fout ("iepuri.out");

int t, a, b, c, n;
int sol[5][5];
int mat[5][5];

void prod(int row, int col, int a[5][5], int b[5][5]){
    int c[5][5];
    for(int i=1; i<=row; i++)
        for(int j=1; j<=col; j++){
            c[i][j]=0;
            for(int l=1; l<=col; l++)
                c[i][j] = (c[i][j] + 1LL * a[i][l] * b[l][j] % MOD) % MOD;

        }

    for(int i=1; i<=row; i++)
        for(int j=1; j<=col; j++)
            a[i][j] = c[i][j];
}

int main (){
    fin>>t;
    while(t--){
        fin>>sol[1][1]>>sol[1][2]>>sol[1][3]>>mat[3][3]>>mat[2][3]>>mat[1][3]>>n;
        mat[2][1]=1;
        mat[3][2]=1;

        n-=2;
        while(n != 0){
            if(n%2 == 1)
                prod(1, 3, sol, mat);
            prod(3, 3, mat, mat);
            n/=2;
        }

        fout<<sol[1][3]<<"\n";

        for(int j=1; j<=3; j++)
            sol[1][j]=0;
        for(int i=1; i<=3; i++)
            for(int j=1; j<=3; j++)
                mat[i][j]=0;
    }
    return 0;
}