#include <bits/stdc++.h>
#define fast ios_base :: sync_with_stdio(0); cin.tie(0);
#pragma GCC optimize("O3")
#define FILE_NAME "iepuri"
#define NMAX 3000 + 100
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> llp;
typedef pair<ld,ld> pct;

const ll inf = 1LL << 60;
const ll mod = 666013;
const ld eps = 1e-9;

ifstream f(FILE_NAME".in");
ofstream g(FILE_NAME".out");

inline void add(ll &a , ll b)
{
    a += b;
    a %= mod;
}

inline void sub(ll &a, ll b)
{
    a = (a - b + mod) % mod;
}
ll a, b, c, n, x, y, z, t,rez[4][4], ans[4][4], pd[4][4];


inline void inm(ll a[4][4],ll b[4][4])
{
    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            rez[i][j] = 0;

    for(int i = 1; i <= 3; ++i)
        for(int k = 1; k <= 3; ++k)
            for(int j = 1; j <= 3; ++j)
                add(rez[i][j], (a[i][k] * b[k][j]) % mod );


    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            a[i][j] = rez[i][j];
}

void logpow(ll b)
{
    while(b)
    {
        if(b & 1)
            inm(ans, pd);
        inm(pd,pd);
        b >>= 1;
    }
}

int main()
{
    ///fast;
    f >> t;
    while(t--)
    {
        f >> x >> y >> z >> a >> b >> c >> n;
        for(int i = 1; i <= 3; ++i)
            for(int j = 1; j <= 3; ++j)
                pd[i][j] = ans[i][j] = 0;

        pd[1][1] = a;
        pd[1][2] = b;
        pd[1][3] = c;
        pd[2][1] = pd[3][2] = 1;
        ans[1][1] = ans[2][2] = ans[3][3] = 1;
        if(n == 0)
            g << z << '\n';
        else if(n == 1)
            g << y << '\n';
        else if(n == 3)
            g << x << '\n';
        else{
            logpow(n - 2);
            ll sol = 0;
            add(sol , (z * ans[1][1]) % mod);
            add(sol , (y * ans[1][2]) % mod);
            add(sol , (x * ans[1][3]) % mod);
            g << sol << '\n';
        }
    }
    f.close();
    g.close();
    return 0;
}