#include <fstream>
#include <vector>

using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
const int Mod = 666013;
using ll = long long;
class Matrix {
    vector <vector <ll>> a;
    ll N;
public:
    Matrix(ll _N) {N = _N; a.resize(N, vector <ll>(N, 0));}
    Matrix(ll _N, ll l) {N = _N; a.resize(N, vector <ll>(N, 0)); for(int i = 0; i < N; i++) a[i][i] = l;}
    Matrix(ll _N, vector <vector <ll>> _a) {N = _N; a = _a;}
    Matrix operator *(const Matrix& other) {
        Matrix res(N);
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * other.a[k][j]) % Mod;
        return res;
    }
    Matrix operator *=(const Matrix& other) {return (*this = *this * other);}
    Matrix exponentiate(ll val) {
        Matrix res(N, 1);
        while(val > 0) {
            if(val & 1) res *= *this;
            *this *= *this;
            val >>= 1;
        }
        return (*this = res);
    }
    vector <ll> operator *(const vector <ll>& v) {
        vector <ll> res(N, 0);
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                res[i] = (res[i] + a[i][j] * v[j]) % Mod;
        return res;
    }
};

int main()
{
    int t, x, y, z, a, b, c, k;
    fin >> t;
    while(t--) {
        fin >> x >> y >> z >> a >> b >> c >> k;
        vector <vector <ll>> v(3, vector <ll>(3, 0));
        v[0][1] = 1; v[1][2] = 1; v[2][0] = c; v[2][1] = b; v[2][2] = a;
        vector <ll> vv(3); vv[0] = x; vv[1] = y; vv[2] = z;
        if(k <= 3) fout << vv[k - 1] << "\n";
        else {
            Matrix M(3, v);
            M.exponentiate(k - 2);
            vv = M * vv;
            fout << vv[2] << "\n";
        }
    }
    return 0;
}