#include<cstdio>
#include<cstring>
#define MOD 666013
using namespace std;
int M[4][4],T,A,B,C,X,Y,Z,N;
void mult(int A[][4],int B[][4]) //A=A*B
{
    int C[4][4],i,j,k;
    memset(C,0,sizeof(C));
    for(i=1;i<=3;i++)
        for(j=1;j<=3;j++)
            for(k=1;k<=3;k++) C[i][j]=(C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
    memcpy(A,C,sizeof(C));
}
void exp(int K)
{
    int P[4][4],i;
    memset(P,0,sizeof(P));
    P[2][1]=1; P[3][2]=1;
    P[1][3]=C; P[2][3]=B; P[3][3]=A;
    for(i=1;i<=K;i<<=1)
    {
        if(i&K) mult(M,P);
        mult(P,P);
    }
}
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&T);
    for(;T;--T)
    {
        scanf("%d%d%d%d%d%d%d",&X,&Y,&Z,&A,&B,&C,&N);
        memset(M,0,sizeof(M));
        M[1][1]=X; M[1][2]=Y; M[1][3]=Z;
        exp(N-2);
        printf("%d\n",M[1][3]);
    }
    return 0;
}