#include <bits/stdc++.h>

using namespace std;

int const mod = 666013;

static void test_case(){
int n;
vector <int> A(3);
vector <vector<int>> B(3,vector<int>(3,0));
for(auto &x:A)cin >> x;
cin >> B[2][2] >> B[1][2] >> B[0][2] >> n;
B[1][0] = B[2][1] = 1;
auto mul1 = [&](vector <int> &A,vector<vector<int>> B)->void{
vector <int> C = A;
for(int i = 0;i < 3; ++i){
    A[i] = 0;
    for(int j = 0;j < 3; ++j)
        A[i] = (1LL*A[i] + 1LL*C[j] * B[j][i]) % mod;
}
};
auto mul2 =[&](vector<vector<int>> &A,vector<vector<int>> B)->void{
for(int i = 0;i < 3; ++i)
    mul1(A[i],B);
};
while (n){
    if(n&1)
        mul1(A,B);
    mul2(B,B);
    n >>= 1;
}
cout << A[0] << "\n";
}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        test_case();

}