#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
int t, x, y, z, a , b, c, n;
int unitate[3][3], mat[3][3], degeaba[3][3];
int normala[3][3];

void inmultire(int A[][3],int B[][3],int C[][3])
{
    for(int i = 0;i < 3;++i)
        for(int j = 0;j < 3;++j)
        {
            C[i][j] = 0;
            for(int k = 0;k < 3;++k)
                    C[i][j] += ((long long) A[i][k] * B[k][j]) % mod;
        }
}

void lgpower(int k)
{
    for(;k;k >>= 1)
    {
        if(k & 1)
            {
                inmultire(unitate,mat,degeaba);
                for(int i = 0;i < 3;++i)
                    for(int j = 0;j < 3;++j)
                        unitate[i][j] = degeaba[i][j];
            }
        inmultire(mat,mat,degeaba);
        for(int i = 0;i < 3;++i)
            for(int j = 0;j < 3;++j)
                mat[i][j] = degeaba[i][j];
    }
}

int Solve()
{
    for(int i = 0;i < 3;++i)
        for(int j = 0;j < 3;++j)
            unitate[i][j] = mat[i][j] = 0;
    for(int i = 0;i < 3;++i)
        unitate[i][i] = 1;
    mat[0][0] = a;
    mat[1][0] = b;
    mat[2][0] = c;
    mat[0][1] = mat[1][2] = 1;
    normala[0][0] = z;
    normala[0][1] = y;
    normala[0][2] = x;
    lgpower(n - 2);
    inmultire(normala,unitate,degeaba);
    return degeaba[0][0];
    //return (((((z * unitate[0][0]) % mod + (y * unitate[1][0]) % mod) % mod + (x * unitate[2][0]) % mod)) % mod) % mod;
}

void Read()
{
    f>>t;
    for(int i = 1;i <= t;++i)
    {
        f>>x>>y>>z>>a>>b>>c>>n;
        g<<Solve()<<'\n';
    }
    f.close();
    g.close();
}

int main()
{
    Read();
    return 0;
}