#include <bits/stdc++.h>
#define mod 666013
const int sz = 3;

using namespace std;

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

struct matrix{
    vector<vector<int>> mat = vector<vector<int>>(sz, vector<int>(sz, 0));
    matrix operator * (const matrix &other) const{
        matrix product;
        for(int i = 0; i < sz; i++)
            for(int j = 0; j < sz; j++)
                for(int k = 0; k < sz; k++)
                    product.mat[i][j] = (product.mat[i][j] + 1LL * mat[i][k] * other.mat[k][j]) % mod;
        return product;
    }
    matrix power(int b){
        matrix product, a = *this;
        for(int i = 0; i < sz; i++)
            product.mat[i][i] = 1;
        while(b){
            if(b & 1)
                product = product * a;
            a = a * a;
            b >>= 1;
        }
        return product;
    }
};

void solve(int x, int y, int zz, int a, int b, int c, int n){
    matrix m, z, rez;
    m.mat[0][0] = x, m.mat[0][1] = y, m.mat[0][2] = zz;
    z.mat[0][0] = 0, z.mat[0][1] = 0, z.mat[0][2] = c;
    z.mat[1][0] = 1, z.mat[1][1] = 0, z.mat[1][2] = b;
    z.mat[2][0] = 0, z.mat[2][1] = 1, z.mat[2][2] = a;
    rez = m * z.power(n - 2);
    fout << rez.mat[0][2] << "\n";
}

void processQueries(){
    int t, x, y, z, a, b, c, n;
    fin >> t;
    for(int i = 1; i <= t; i++){
        fin >> x >> y >> z >> a >> b >> c >> n;
        solve(x, y, z, a, b, c, n);
    }
}

int main()
{
    processQueries();
    return 0;
}