#include <stdio.h>
#include <stdlib.h>
#define MOD 666013
long long aux[3][3],add[3][3],rez[3][3];
void prod(long long a[3][3],long long b[3][3])
{
    int i,j,k;
    for(i=0; i<3; i++)
        for(j=0; j<3; j++)
            aux[i][j]=0;
    for(i=0; i<3; i++)
        for(j=0; j<3; j++)
            for(k=0; k<3; k++)
                aux[i][j]=(aux[i][j]+a[i][k]*b[k][j])%MOD;
    for(i=0; i<3; i++)
        for(j=0; j<3; j++)
            a[i][j]=aux[i][j];
}
void exp(long long a[3][3],int b)
{
    long long aux1[3][3];
    int i,j;
    if(b==1)
    {
        for(i=0; i<3; i++)
            for(j=0; j<3; j++)
                aux1[i][j]=0;
        aux1[0][0]=aux1[1][1]=aux1[2][2]=1;
        prod(a,aux1);
    }
    else
    {
        for(i=0; i<3; i++)
            for(j=0; j<3; j++)
                aux1[i][j]=a[i][j];
        prod(a,aux1);
        exp(a,b/2);
        if(b%2==1)
            prod(a,aux1);
    }
}
int main()
{
    int k,i,j,x,y,z,a,b,c,n,t;
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    scanf("%d",&t);
    for(k=1; k<=t; k++)
    {
        scanf("%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&n);
        rez[0][0]=rez[0][1]=rez[0][2]=rez[1][0],rez[1][1]=rez[1][2]=rez[1][3]=0;
        rez[2][0]=x;
        rez[2][1]=y;
        rez[2][2]=z;
        add[0][0]=add[0][1]=add[1][1]=add[2][0]=0;
        add[1][0]=add[2][1]=1;
        add[0][2]=c;
        add[1][2]=b;
        add[2][2]=a;
        exp(add,n-2);
        prod(rez,add);
        printf("%lld\n",rez[2][2]);
    }

    return 0;
}