#include <cstdio>
#include <cstring>
#define mod 666013

using namespace std;

int v[4][4],sol[4][4],aux[4][4];
int t,x,y,z,n,i,j,q,p;

int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);
    for(scanf("%d",&t);t;t--)
    {
        memset(v,0,sizeof(v));
        memset(sol,0,sizeof(sol));
        v[2][1]=v[3][2]=1;
        scanf("%d%d%d%d%d%d%d",&sol[1][1],&sol[1][2],&sol[1][3],&v[3][3],&v[2][3],&v[1][3],&n);
        n-=2;
        for(p=1;p<=n;p<<=1)
        {
            if(n&p)
            {
                memset(aux,0,sizeof(aux));
                for(i=1;i<=3;i++)
                    for(j=1;j<=3;j++)
                        for(q=1;q<=3;q++)
                            aux[i][q]=(aux[i][q]+1LL*sol[i][j]*v[j][q])%mod;
                memcpy(sol,aux,sizeof(aux));
            }
            memset(aux,0,sizeof(aux));
            for(i=1;i<=3;i++)
                for(j=1;j<=3;j++)
                    for(q=1;q<=3;q++)
                        aux[i][q]=(aux[i][q]+1LL*v[i][j]*v[j][q])%mod;
            memcpy(v,aux,sizeof(aux));
        }
        printf("%d\n",sol[1][3]);
    }
    return 0;
}