#include<iostream>
#include <cstdio>
#include <cstring>
#define mod 666013
using namespace std;
long long  sol[4][4],n;
int A,B,C,t;
void inmultire(long long a[4][4],long long b[4][4], long long c[4][4])
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        for(int k=0;k<3;k++)
        c[i][j]=(c[i][j]+((a[i][k]%mod)*(b[k][j]%mod))%mod)%mod;
}
void lg_putere(long long  sol[4][4],long long p )
{
    long long m[4][4],aux[4][4];
    memset(m,0,sizeof(m));
    m[0][2]=C;
    m[1][2]=B;
    m[2][2]=A;
    m[1][0]=1;
    m[2][1]=1;
    while(p>=1)
        {if(1&p)
        {
            memset(aux,0,sizeof(aux));
            inmultire(sol,m,aux);
            memcpy(sol,aux,sizeof(aux));
            p--;
        }
        memset(aux,0,sizeof(aux));
        inmultire(m,m,aux);
        memcpy(m,aux,sizeof(m));
        p>>=1;
    }

}
int x,y,z;

int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        memset(sol,0,sizeof(sol));
        scanf("%d%d%d%d%d%d%lld",&x,&y,&z,&A,&B,&C,&n);
    sol[0][0]=x;
    sol[0][1]=y;
    sol[0][2]=z;
    lg_putere(sol,n-2);
    printf("%ld\n",sol[0][2]);
    }
}