#include <fstream>
#define mF "iepuri"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
using LL = long long;
const int M = 666013;
#define F(i) for (int i = 0; i < 3; i++)
struct X
{
    LL A[3][3];
    LL* operator [] (int i) {return A[i];}
    X operator * (X B) {X C = {}; F(i) F(j) F(k) (C[i][j] += A[i][k] * B[k][j]) %= M; return C;}
};
int main()
{
    int t; in >> t; while (t--)
    {
        int x, y, z, n; X Z = {{{}, {1}, {0, 1}}}, R = {{{1}, {0, 1}, {0, 0, 1}}};
        in >> x >> y >> z >> Z[2][2] >> Z[1][2] >> Z[0][2] >> n;
        for (; n; n >>= 1) {if (n & 1) R = R * Z; Z = Z * Z;}
        out << (X{{{x, y, z}}} * R)[0][0] << '\n';
    }
}