#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

#define N 666013
void multiply(vector<vector<ll>> &a, vector<vector<ll>> &b){
    vector<vector<ll>> c(3, vector<ll>(3));
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            for(int k = 0; k < 3; k++){
                c[i][j] += (a[i][k] * b[k][j]) % N;
                c[i][j] %= N;
            }
        }
    }
    for(int i = 0; i<3; i++){
        for(int j = 0; j<3; j++) a[i][j] = c[i][j];
    }
}
vector<vector<ll>> matrix_fast_exp(vector<vector<ll>> &a, ll n){
    vector<vector<ll>> t(3, vector<ll>(3));
    t = {{1,0,0}, {0,1,0}, {0,0,1}};
    if(n == 0) return t;
    if(n == 1) return a;
    while(n > 0){
        if(n % 2 == 1)
            multiply(t, a);
        multiply(a, a);
        n /= 2;
    }

    return t;
}
void test(){
    int x,y,z,a,b,c;
    ll n;
    fin >> x >> y >> z >> a >> b >> c >> n;
    vector<vector<ll>> m = {
        {a, b, c},
        {1,0,0},
        {0,1,0},
    };
    vector<vector<ll>> t = {
        {z,0,0},
        {y,0,0},
        {x,0,0}
    };
    vector<vector<ll>> ans = matrix_fast_exp(m, n-2);
    multiply(ans, t);
    fout << ans[0][0] << '\n';

}

int main(){
    int t;
    fin >> t;
    while(t--){
        test();
    }

    return 0;
}