#include <fstream>
#include <cstring>
#define MOD 666013

using namespace std;

void mul(int A[][3], int B[][3])
{
    int C[3][3];
    for(int i = 0; i < 3; ++i)
        for(int j = 0; j < 3; ++j)
        {
            long long aux = 0;
            for(int k = 0; k < 3; ++k)
                aux += ((long long)A[i][k]) * B[k][j];
            C[i][j] = aux % MOD;
        }
    memcpy(A, C, sizeof(C));
}

int putere(int n, int P[3][3], int A[3][3])
{

    while(n > 0)
    {
        while((n & 1) == 0)
        {
            mul(A, A);
            n >>= 1;
        }
        mul(P, A);
        n--;
    }
    return P[0][2];
}

int main()
{
    int A[3][3] = {{0, 0, 9}, {1, 0, 9}, {0, 1, 9}}, C[3][3] = {{0, 0, 9}, {1, 0, 9}, {0, 1, 9}};
    int P[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}}, n, t;
    ifstream fin("iepuri.in");
    ofstream fout("iepuri.out");
    fin>>t;
    while(t--)
    {
        fin >> P[0][0]>>P[0][1]>>P[0][2]>>A[2][2]>>A[1][2]>>A[0][2]>>n;
        fout<< putere(n - 2, P, A);
        memcpy(A, C, sizeof(C));
    }
    fin.close();
    fout.close();
    return 0;
}