#include <iostream>
#include<cstdio>
#define mod 666013
using namespace std;
long long a,b,c,A[2][4],I[4][4],CI[4][4];
long long ridic(int exp, int a, int b, int c)
{
    int i,j;
    long long rez[4][4];
    I[2][1]=1;
    I[3][2]=1;
    I[1][3]=c;
    I[2][3]=b;
    I[3][3]=a;
    I[1][1]=0;
    I[1][2]=0;
    I[2][2]=0;
    I[3][1]=0;
    rez[1][1]=1;
    rez[1][2]=0;
    rez[1][3]=0;
    rez[2][2]=1;
    rez[2][1]=0;
    rez[2][3]=0;
    rez[3][3]=1;
    rez[3][1]=0;
    rez[3][2]=0;
    while(exp)
    {
        if(exp%2==1)
        {
            for(i=1; i<=3; i++)
                for(j=1; j<=3; j++)
                    CI[i][j]=rez[i][j];
            rez[1][1]=(CI[1][1]*I[1][1]+CI[1][2]*I[2][1]+CI[1][3]*I[3][1])%mod;
            rez[1][2]=(CI[1][1]*I[1][2]+CI[1][2]*I[2][2]+CI[1][3]*I[3][2])%mod;
            rez[1][3]=(CI[1][1]*I[1][3]+CI[1][2]*I[2][3]+CI[1][3]*I[3][3])%mod;
            rez[2][1]=(CI[2][1]*I[1][1]+CI[2][2]*I[2][1]+CI[2][3]*I[3][1])%mod;
            rez[2][2]=(CI[2][1]*I[1][2]+CI[2][2]*I[2][2]+CI[2][3]*I[3][2])%mod;
            rez[2][3]=(CI[2][1]*I[1][3]+CI[2][2]*I[2][3]+CI[2][3]*I[3][3])%mod;
            rez[3][1]=(CI[3][1]*I[1][1]+CI[3][2]*I[2][1]+CI[3][3]*I[3][1])%mod;
            rez[3][2]=(CI[3][1]*I[1][2]+CI[3][2]*I[2][2]+CI[3][3]*I[3][2])%mod;
            rez[3][3]=(CI[3][1]*I[1][3]+CI[3][2]*I[2][3]+CI[3][3]*I[3][3])%mod;
            exp--;
        }
        else
        {
            for(i=1; i<=3; i++)
                for(j=1; j<=3; j++)
                    CI[i][j]=I[i][j];
            I[1][1]=(CI[1][1]*CI[1][1]+CI[1][2]*CI[2][1]+CI[1][3]*CI[3][1])%mod;
            I[1][2]=(CI[1][1]*CI[1][2]+CI[1][2]*CI[2][2]+CI[1][3]*CI[3][2])%mod;
            I[1][3]=(CI[1][1]*CI[1][3]+CI[1][2]*CI[2][3]+CI[1][3]*CI[3][3])%mod;
            I[2][1]=(CI[2][1]*CI[1][1]+CI[2][2]*CI[2][1]+CI[2][3]*CI[3][1])%mod;
            I[2][2]=(CI[2][1]*CI[1][2]+CI[2][2]*CI[2][2]+CI[2][3]*CI[3][2])%mod;
            I[2][3]=(CI[2][1]*CI[1][3]+CI[2][2]*CI[2][3]+CI[2][3]*CI[3][3])%mod;
            I[3][1]=(CI[3][1]*CI[1][1]+CI[3][2]*CI[2][1]+CI[3][3]*CI[3][1])%mod;
            I[3][2]=(CI[3][1]*CI[1][2]+CI[3][2]*CI[2][2]+CI[3][3]*CI[3][2])%mod;
            I[3][3]=(CI[3][1]*CI[1][3]+CI[3][2]*CI[2][3]+CI[3][3]*CI[3][3])%mod;
            exp/=2;

        }
    }
    CI[1][1]=(A[1][1]*rez[1][1]+A[1][2]*rez[2][1]+A[1][3]*rez[3][1])%mod;
    CI[1][2]=(A[1][1]*rez[1][2]+A[1][2]*rez[2][2]+A[1][3]*rez[3][2])%mod;
    CI[1][3]=(A[1][1]*rez[1][3]+A[1][2]*rez[2][3]+A[1][3]*rez[3][3])%mod;
    return CI[1][3];
}
int main()
{
    freopen("iepuri.in","r",stdin);
    freopen("iepuri.out","w",stdout);
    int i,t,n;
    scanf("%d",&t);
    for(i=1; i<=t; i++)
    {
        scanf("%lld%lld%lld%lld%lld%lld%d", &A[1][1],&A[1][2],&A[1][3],&a,&b,&c,&n);
        printf("%lld\n", ridic(n-2,a, b,c));
    }
    return 0;
}