#include <iostream>
#include<cstdio>
#define mod 666013
using namespace std;
long long a,b,c,m[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]=(m[1][1]*rez[1][1]+m[1][2]*rez[2][1]+m[1][3]*rez[3][1])%mod;
    CI[1][2]=(m[1][1]*rez[1][2]+m[1][2]*rez[2][2]+m[1][3]*rez[3][2])%mod;
    CI[1][3]=(m[1][1]*rez[1][3]+m[1][2]*rez[2][3]+m[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", &m[1][1],&m[1][2],&m[1][3],&a,&b,&c,&n);
        printf("%lld\n", ridic(n-2,a, b,c));
    }
    return 0;
}