#include<bits/stdc++.h>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
const int mod = 666013;
long long n;
long long a[5];
long long x, y, z;
long long d, e, ff, nrd;
long long mat[5][5];
void mult(long long a[5][5], long long b[5][5])
{
    long long ans[5][5];
    for(long long i = 1; i <= 3; ++i)
        for(long long j = 1; j <= 3; ++j)
            ans[i][j] = 0;
    for(long long i = 1; i <= 3; ++i)
        for(long long j = 1; j <= 3; ++j)
            for(long long k = 1; k <= 3; ++k)
                ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % mod;
    for(long long i = 1; i <= 3; ++i)
        for(long long j = 1; j <= 3; ++j)
            a[i][j] = ans[i][j];
}
void lgput(long long a[5][5], long long p)
{
    long long copie[5][5];
    for(long long i = 1; i <= 3; ++i)
        for(long long j = 1; j <= 3; ++j)
        {
            copie[i][j] = a[i][j];
            if(i == j)
                a[i][j] = 1;
            else
                a[i][j] = 0;
        }
    while(p)
    {
        if(p & 1)
            mult(a, copie);
        mult(copie, copie);
        p >>= 1;
    }
}
int main()
{
    f >> n;
    for(; n; --n)
    {
        f >> x >> y >> z >> d >> e >> ff >> nrd;
        memset(a, 0, sizeof(a));
        memset(mat, 0, sizeof(mat));
        a[1] = z, a[2] = y, a[3] = x;
        mat[1][1] = d, mat[1][2] = e, mat[1][3] = ff;
        mat[2][1] = mat[3][2] = 1;
        if(nrd <= 2)
            g << a[nrd + 1] << '\n';
        else
        {
            lgput(mat, nrd - 2);
            long long ans[4];
            for(int j = 1; j <= 3; ++j)
                ans[j] = 0;
            for(int i = 1; i <= 3; ++i)
                for(int k = 1; k <= 3; ++k)
                    ans[i] = (ans[i] + mat[i][k] * a[k]) % mod;
            g << ans[1] << '\n';
        }
    }
    return 0;
}