#include <cstdio>
#include <cstring>
#define mod 666013
using namespace std;
int t, n, i, 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(i=0;(1<<i)<=n;i++)
        {
            if(n&(1<<i))
            {
                memset(aux, 0, sizeof(aux));
                multi(A, b, aux);
                memcpy(A, aux, sizeof(aux));
            }
            memset(aux, 0, sizeof(aux));
            multi(b, b, aux);
            memcpy(b, aux, sizeof(aux));
        }

        printf("%d\n", A[2][2]);
    }
    return 0;
}
/*void log_pw(int x, int m[][4])
{
    int i, aux[4][4], b[4][4];
    memcpy(b, Z, sizeof(Z));
    for(i=0;(1<<i)<=x;i++)
    {
        if(x&(1<<i))
        {
            memset(aux, 0, sizeof(aux));
            multi(m, b, aux);
            memcpy(m, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        multi(b, b, aux);
        memcpy(b, aux, sizeof(aux));
    }
}*/
void multi(int a[][4], int b[][4], int c[][4])
{
    int i, j, k;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            for(k=0;k<3;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%mod;
}