#include<bits/stdc++.h>
using namespace std;
ifstream F("iepuri.in");
ofstream G("iepuri.out");
int n,t,x,y,z,m=666013,i,j,e[3][3],f[3][3],d[3][3];
void A(int c[][3],int a[][3],int b[][3])
{
    int i,j,k;
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            for(c[i][j]=0,k=0;k<3;c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%m,++k);
}
void B(int a[][3],int b[][3])
{
    int i,j;
    for(i=0;i<3;++i)
        for(j=0;j<3;a[i][j]=b[i][j],++j);
}
int main()
{
    for(F>>t;t--;G<<(1LL*x*f[2][0]+1LL*y*f[2][1]+1LL*z*f[2][2])%m<<'\n')
        for(F>>x>>y>>z>>e[2][2]>>e[2][1]>>e[2][0]>>n,f[0][0]=f[1][1]=f[2][2]=e[0][1]=e[1][2]=1,f[0][1]=f[0][2]=f[1][0]=f[1][2]=f[2][0]=f[2][1]=e[0][0]=e[0][2]=e[1][0]=e[1][1]=0,n-=2;n;A(d,e,e),B(e,d),n>>=1)
            if(n&1)
                A(d,e,f),B(f,d);
    return 0;
}