#include<stdio.h>
#define mod 666013
struct mat
{
    int m[4][4];

};
mat prod(mat a, mat b)
{
    int i,j,z;
    mat c;
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
        {
            c.m[i][j]=0;
            for(z=1;z<=3;z++)
                c.m[i][j]=(1LL*c.m[i][j]+(1LL*a.m[i][z]*b.m[z][j])%mod)%mod;
        }
    return c;

}
mat lgput(mat a, int k)
{
    if(k==1)
        return a;
    if(k%2==0)
        return lgput(prod(a,a),k/2);
    return prod(lgput(prod(a,a),(k-1)/2),a);
}
int k,t;
mat sol,e,d,sol1;
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    while(t)
    {
         for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
               sol1.m[i][j]=sol.m[i][j]=d.m[i][j]=e.m[i][j]=0;
        }

        scanf("%d%d%d",&d.m[1][1],&d.m[2][1],&d.m[3][1]);
        scanf("%d%d%d",&e.m[3][3],&e.m[3][2],&e.m[3][1]);
        scanf("%d",&k);
       // k++;
        k-=2;
        e.m[1][2]=1;
        e.m[2][3]=1;
        sol1=lgput(e,k);

        sol=prod(sol1,d);
         /*for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
                printf("%d ",sol1.m[i][j]);
             printf("\n");
        }*/
        printf("%d\n",sol.m[3][1]);
        t--;
    }
    return 0;

}