#include<stdio.h>
int a[4][4],b[4][4],X,Y,Z,A,B,C,N,T;
void mul(int a[4][4], int x, int b[4][4])
{
    int c[4][4];
    for(int i=1;i<=x;++i)
        for(int j=1;j<=3;++j)
            c[i][j]=0;
    for(int i=1;i<=x;++i)
        for(int j=1;j<=3;++j)
            for(int k=1;k<=3;++k)
            {
                c[i][j]=(c[i][j]+(1LL*a[i][k]*b[k][j])%666013)%666013;
            }
    for(int i=1;i<=x;++i)
        for(int j=1;j<=3;++j)
            a[i][j]=c[i][j];
}
void powy(int b[4][4],int x)
{
    int d[4][4];
    for(int i=1;i<=3;++i)
        for(int j=1;j<=3;++j)
            d[i][j]=b[i][j];
    if(x==1)
        return;
    powy(b,x/2);
    if(x%2==0)
        mul(b,3,b);
    else
    {
        mul(b,3,b);
        mul(b,3,d);
    }
}
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
    {
        scanf("%d%d%d%d%d%d%d",&X,&Y,&Z,&A,&B,&C,&N);
        if(N==0)
            printf("%d\n",X);
        else if(N==1)
            printf("%d\n",Y);
        else if(N==2)
            printf("%d\n",Z);
        else
        {
            b[1][1]=0;
            b[1][2]=0;
            b[2][1]=1;
            b[2][2]=0;
            b[3][1]=0;
            b[3][2]=1;
            b[1][3]=C;
            b[2][3]=B;
            b[3][3]=A;
            a[1][1]=X;
            a[1][2]=Y;
            a[1][3]=Z;
            powy(b,N-2);
            mul(a,1,b);
            printf("%d\n",a[1][3]);
        }
    }
    return 0;
}