#include <cstdio>

using namespace std;
const int mod=666013;

int v1[3],v2[3];

struct matrice
{
    int v[3][3];
    matrice()
    {
        for(int i=0;i<=2;i++)
            for(int j=0;j<=2;j++)
                v[i][j]=0;
    }
    matrice operator *(matrice p)
    {
        matrice a;
        for(int i=0;i<=2;i++)
            for(int j=0;j<=2;j++)
                for(int k=0;k<=2;k++)
                    a.v[i][j]=(a.v[i][j]+1LL*v[i][k]*p.v[k][j])%mod;
        return a;
    }
};

matrice rid_putere(matrice p,int n)
{
    matrice rez;
    for(int i=0;i<=2;i++)
        rez.v[i][i]=1;
    for(long long i=1;i<=n;i<<=1)
    {
        if(n&i) rez=rez*p;
        p=p*p;
    }
    return rez;
}

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    int t,x,y,z,a,b,c,n;
    scanf("%d",&t);
    for(int test=1;test<=t;test++)
    {
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        matrice p;
        for(int i=0;i<=2;i++) v2[i]=0;
        p.v[1][0]=1;p.v[2][1]=1;p.v[0][2]=c;p.v[1][2]=b;p.v[2][2]=a;
        p=rid_putere(p,n-2);
        v1[0]=x;v1[1]=y;v1[2]=z;
        for(int i=0;i<=2;i++)
            for(int j=0;j<=2;j++)
                v2[i]=(v2[i]+1LL*v1[j]*p.v[j][i])%mod;
        printf("%d\n",v2[2]);
    }
    return 0;
}