#include <bits/stdc++.h>
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
#define int long long
const int Max = 1e5 + 1;
const int MOD = 666013;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
struct matrice{
    int val[5][5];
};
matrice operator * (matrice m1, matrice m2)
{
    matrice ans;
    int i,j,k;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        ans.val[i][j] = 0;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
    {
        for(k=1;k<=3;k++)
        {
            ans.val[i][j] += m1.val[i][k] * m2.val[k][j];
            ans.val[i][j]%=MOD;
        }
    }
    return ans;
}
int x,y,z,a,b,c,n;
void set_0(matrice &m)
{
    int i,j;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        m.val[i][j] = 0;
}
void read()
{
    f>>x>>y>>z>>a>>b>>c>>n;
}
void afis_mat(matrice a)
{
    int i,j;
    for(i=1;i<=3;i++)
    {
        for(j=1;j<=3;j++)
            cout<<a.val[i][j]<<' ';
        cout<<'\n';
    }
    cout<<'\n';
}
matrice fastpow(matrice base, int exp)
{
    if(exp == 0)
    {
        matrice I3;
        set_0(I3);
        int i;
        for(i=1;i<=3;i++)
            I3.val[i][i] = 1;
        return I3;
    }
    matrice rad = fastpow(base,exp / 2);
    rad = rad * rad;
    if(exp%2!=0)
        rad = rad * base;
    return rad;
}
int get_val()
{
    matrice mat;
    set_0(mat);
    mat.val[1][1] = a;
    mat.val[1][2] = b;
    mat.val[1][3] = c;
    mat.val[2][1] = 1;
    mat.val[3][2] = 1;
    mat = fastpow(mat,n-2);
    int i;
    int ans = z*mat.val[1][1] + y*mat.val[1][2] + x*mat.val[1][3];
    ans%=MOD;
    return ans;
}

void teste()
{
    matrice M1;
    int i,j;

}
void solve()
{
    g<<get_val()<<'\n';
}
void restart()
{

}

int32_t main()
{
    nos();
    int teste;
    f>>teste;
    while(teste--)
    {
        read();
        solve();
        restart();
    }
    return 0;
}