#include <cstdio>
#include <cstring>
#define mod 666013
using namespace std;
int t, n, ii, i, j, k, aux[4][4], b[4][4], A[4][4], Z[4][4];
void log_pw(int x, int m[][4]);
void multi(int a[][4], int b[][4], int c[4][4]);
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++)
                        for(k=0;k<3;k++)
                            aux[i][j]=(aux[i][j]+1LL*A[i][k]*b[k][j])%mod;

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

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

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

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