#include <cstdio>

using namespace std;

#define mod 666013

int e[4];
int m[5][5],m1[5][5];
int nul[5][5];
void cpy(int a[5][5],int b[5][5])
{
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            a[i][j]=b[i][j]%mod;
}
void inmult(int a[5][5],int b[5][5])
{
    int aux1[5][5];
    aux1[1][1]=((1LL*a[1][1]*b[1][1])%mod+(1LL*a[1][2]*b[2][1])%mod+(1LL*a[1][3]*b[3][1])%mod)%mod;
    aux1[1][2]=((1LL*a[1][1]*b[1][2])%mod+(1LL*a[1][2]*b[2][2])%mod+(1LL*a[1][3]*b[3][2])%mod)%mod;
    aux1[1][3]=((1LL*a[1][1]*b[1][3])%mod+(1LL*a[1][2]*b[2][3])%mod+(1LL*a[1][3]*b[3][3])%mod)%mod;
    aux1[2][1]=((1LL*a[2][1]*b[1][1])%mod+(1LL*a[2][2]*b[2][1])%mod+(1LL*a[2][3]*b[3][1])%mod)%mod;
    aux1[2][2]=((1LL*a[2][1]*b[1][2])%mod+(1LL*a[2][2]*b[2][2])%mod+(1LL*a[2][3]*b[3][2])%mod)%mod;
    aux1[2][3]=((1LL*a[2][1]*b[1][3])%mod+(1LL*a[2][2]*b[2][3])%mod+(1LL*a[2][3]*b[3][3])%mod)%mod;
    aux1[3][1]=((1LL*a[3][1]*b[1][1])%mod+(1LL*a[3][2]*b[2][1])%mod+(1LL*a[3][3]*b[3][1])%mod)%mod;
    aux1[3][2]=((1LL*a[3][1]*b[1][2])%mod+(1LL*a[3][2]*b[2][2])%mod+(1LL*a[3][3]*b[3][2])%mod)%mod;
    aux1[3][3]=((1LL*a[3][1]*b[1][3])%mod+(1LL*a[3][2]*b[2][3])%mod+(1LL*a[3][3]*b[3][3])%mod)%mod;
    cpy(a,aux1);
}
void lgput(int n)
{
    bool ok=0;
    while(n)
    {
        if(n%2==1)
        {
            if(ok==0)
                cpy(m1,m),ok=1;
            else
                inmult(m1,m);
        }
        inmult(m,m);
        n/=2;
    }
}
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
    int x,y,z,a,b,c,n;
    scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
    e[1]=x%mod;
    e[2]=y%mod;
    e[3]=z%mod;
    m[2][1]=1;m[3][2]=1;m[1][3]=c%mod;m[2][3]=b%mod;m[3][3]=a%mod;
    lgput(n);
    printf("%d\n",((1LL*e[1]*m1[1][1])%mod+(1LL*e[2]*m1[2][1])%mod+(1LL*e[3]*m1[3][1])%mod)%mod);
    cpy(m,nul);cpy(m1,nul);
    }
    return 0;
}