#include <bits/stdc++.h>
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
typedef long long ll;
const int mod=666013;
int rez[5][5],m[5][5];
int cc[5][5],f[5][5];
void rez_m()
{
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
        cc[i][j]=0;
    for(int k=1;k<=3;++k)
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
        cc[i][j]=(cc[i][j]+m[i][k]*rez[k][j])%mod;
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
        rez[i][j]=cc[i][j];
}
void m_m()
{
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
        cc[i][j]=0;
    for(int k=1;k<=3;++k)
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
        cc[i][j]=(cc[i][j]+m[i][k]*m[k][j])%mod;
    for(int i=1;i<=3;++i)
    for(int j=1;j<=3;++j)
        m[i][j]=cc[i][j];
}
int main()
{
    int tst,x,y,z,a,b,c,n;
    in>>tst;
    while(tst--)
    {
        in>>x>>y>>z>>a>>b>>c>>n;
        if(n==0) {out<<x<<'\n';continue;}
        if(n==1) {out<<x<<'\n';continue;}
        if(n==2) {out<<x<<'\n';continue;}
        for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j)
            rez[i][j]=cc[i][j]=m[i][j]=f[i][j]=0;
        rez[1][1]=rez[2][2]=rez[3][3]=1;
        m[1][3]=c; m[2][1]=1; m[2][3]=b;
        m[3][2]=1; m[3][3]=a;
        n-=2;
        while(n)
        {
            if(n&1) rez_m();
            m_m();
            n>>=1;
        }
        f[1][1]=x; f[1][2]=y; f[1][3]=z;
        cc[1][1]=cc[1][2]=cc[1][3]=0;
        for(int k=1;k<=3;++k)
        for(int j=1;j<=3;++j)
            cc[1][j]=(cc[1][j]+f[1][k]*rez[k][j])%mod;
        out<<cc[1][3]<<'\n';
    }
    return 0;
}