#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
int x,y,z,a,b,c;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
using Matrix = vector < vector < long long> >;
const long long mod = 666013;
const long long k = 3;

Matrix mult(Matrix A, Matrix B) {

    Matrix res(k+1,vector<long long>(k+1));///initalizare de vector
    for ( long long i = 1; i <= k; ++i)
        for ( long long j = 1; j <= k; ++j)
            for ( long long w = 1; w <= k ;++ w) {
                res[i][j] = (res[i][j] + A[i][w] *B[w][j])%mod;
            }
    return res;
}

Matrix pow(Matrix A, long long p) {
    if(p == 1)
        return A;
    if(p % 2==1)
            return mult(A,pow(A,p-1));
    Matrix X = pow(A,p/2);
    return mult(X,X);

}

int test() {
    long long n;
    fin >>x>>y>>z>>a>>b>>c>>n;
    if(n == 1 or n == 2) {
        fout << 1;
        return 0;
    }
    Matrix T(k+1,vector < long long> (k+1));
    T[1][1] = a; T[1][2] = 1; T[1][3]= 0;
    T[2][1] = b; T[2][2] = 0; T[2][3]=1;
    T[3][1] = c; T[3][2] = 0; T[3][3]=0;
    T = pow(T,n-2);
    vector < long long> f(4);
    f[0] = a;
    f[1] = z;
    f[2] = y;
    f[3] = x;
    long long res = 0;
    for ( long long i = 1; i <= k; ++i) {
        res = (res + T[i][1] * f[i])%mod;
    }
    fout << res;
}

int main()
{
    int t;
    fin>>t;
    for (int i=1;i<=t;i++) test();
}