#include <bits/stdc++.h>
#define mod 666013
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
long long sol[4][4];
void inm(long long a[][4],long long b[][4])
{
    long long c[4][4],i,j,k;
    memset(c,0,sizeof(c));
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            for(k=0;k<3;k++)
                c[i][j]=(c[i][j]+a[i][k]*b[k][j])%mod;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            a[i][j]=c[i][j];
}

void put(long long  a[][4],long long p)
{
    memset(sol,0,sizeof(sol));
    sol[0][0]=sol[1][1]=sol[2][2]=1;
    for(int i=0;(1<<i)<=p;i++)
    {
        if((1<<i)&p)
        {
            inm(sol,a);
        }
        inm(a,a);
    }
}

int main()
{long long t,a,b,c,x,y,z,n;
long long m[4][4];
in>>t;
while(t--)
{
    in>>x>>y>>z>>a>>b>>c>>n;
    memset(m,0,sizeof(m));
    m[0][0]=x;
    m[0][1]=y;
    m[0][2]=z;
    m[1][0]=m[2][1]=1;
    put(m,n-2);
    out<<((a*sol[0][0])%mod+(b*sol[0][1])%mod+(c*sol[0][2])%mod)%mod<<'\n';
}
    return 0;
}