#include <cstdio>
#include <string.h>
#define modul 666013
int x,y,z,a,b,c,n;
long long p[4][4],sol[4][4],temp[4][4];
void produs(long long v1[4][4],long long v2[4][4],long long v3[4][4])
{
    int i,j,k;
    for(i=1;i<=3;++i)
        for(j=1;j<=3;++j)
            for(k=1;k<=3;++k)
                v3[i][j]=(v3[i][j]+v1[i][k]*v2[k][j])%modul;
}
void solve()
{
    int k;
    memset(p,0,sizeof(p));
    memset(sol,0,sizeof(sol));
    p[1][2]=p[2][3]=1;
    p[3][1]=c;p[3][2]=b;p[3][3]=a;
    sol[1][1]=sol[2][2]=sol[3][3]=1;
    for (k=0;k<32;k++)
    {
        if ((n>>k)&1)
        {
            memset(temp,0,sizeof(temp));
            produs(p,sol,temp);
            memcpy(sol,temp,sizeof(temp));
        }
        memset(temp,0,sizeof(temp));
        produs(p,p,temp);
        memcpy(p,temp,sizeof(p));
    }
    int afis=(x*sol[1][1]+y*sol[1][2]+z*sol[1][3])%modul;
    printf("%d\n",afis);
}
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    int i,t;
    scanf("%d\n",&t);
    for (i=1;i<=t;++i)
    {
        scanf("%d %d %d %d %d %d %d",&x,&y,&z,&a,&b,&c,&n);
        solve();
    }
    return 0;
}