#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 666013;
using matrix = vector<vector<ll>>;
int t;
matrix mul(const matrix& a, const matrix& b)
{
    int n = a.size();
    matrix c(n,vector<ll>(n,0));
    for(int i = 0; i < n; i++)
    {
        for(int k = 0; k < n; k++)
        {
            if(a[i][k] == 0)
                continue;
            for(int j = 0; j < n; j++)
                c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD;
        }
    }
    return c;
}

matrix log_pow(matrix base, ll pow)
{
    int n = base.size();
    matrix c(n,vector<ll>(n,0));
    for(int i = 0; i <n;i++)
        c[i][i] = 1;//matricea identica
    while(pow)
    {
        if(pow & 1)
            c = mul(c,base);
        base = mul(base,base);
        pow >>= 1;
    }
    return c;
}

void solve()
{
    int x,y,z,a,b,c;
    long long n;
    cin >> x >> y >> z >> a >> b >> c >> n;
    if(n == 0)
    {
        cout << x << '\n';
        return;
    }
    if(n == 1)
    {
        cout << y << '\n';
        return;
    }
    if(n == 2)
    {
        cout << z << '\n';
        return;
    }
    matrix m = {{a,b,c},{1,0,0},{0,1,0}};
    matrix ans = log_pow(m,n-2);
    ll fn = (ans[0][0]*z + ans[0][1]*y + ans[0][2]*x) % MOD;
    cout << fn << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while(t--)
        solve();
    return 0;
}