#include <cstdio>
#include <cstring>
#define mod 666013
using namespace std;
int t, n, ii, i, j, k, aux[3][3], b[3][3], A[3][3], Z[3][3];
long long s;
int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    scanf("%d", &t);
    while(t--)
    {
        memset(A, 0, sizeof(A));
        scanf("%d%d%d", &A[2][0], &A[2][1], &A[2][2]);
        scanf("%d%d%d", &Z[2][2], &Z[1][2], &Z[0][2]);
        scanf("%d", &n);
        n-=2;
        Z[1][0]=1;
        Z[2][1]=1;

        memcpy(b, Z, sizeof(Z));
        for(ii=0;(1<<ii)<=n;ii++)
        {
            if(n&(1<<ii))
            {
                memset(aux, 0, sizeof(aux));

                for(i=0;i<3;i++)
                    for(j=0;j<3;j++)
                    {
                        s=0;
                        for(k=0;k<3;k++)
                        {
                            s+=1LL*A[i][k]*b[k][j];
                            aux[i][j]=s%mod;
                        }
                    }

                memcpy(A, aux, sizeof(aux));
            }
            memset(aux, 0, sizeof(aux));

            for(i=0;i<3;i++)
                for(j=0;j<3;j++)
                {
                    s=0;
                    for(k=0;k<3;k++)
                    {
                        s+=1LL*b[i][k]*b[k][j];
                        aux[i][j]=s%mod;
                    }
                }

            memcpy(b, aux, sizeof(aux));
        }

        printf("%d\n", A[2][2]);
    }
    return 0;
}