#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream in("iepuri.in");
ofstream out("iepuri.out");
typedef unsigned long long ull;
int A,B,C,x,y,z,dco,n;
ull a[5][5],b[5][5];

void reset( ull mat[5][5]){
    for(int i=1;i<=3;++i){
            for(int j=1;j<=3;++j)
                mat[i][j]=0;
        }
}

 void inm(ull a[5][5], ull b[5][5]){
    unsigned long long c[5][5];
    int i,j;
    c[1][1]=(1LL*a[1][1]*b[1][1]%mod+1LL*a[1][2]*b[2][1]%mod+1LL*a[1][3]*b[3][1]%mod)%mod;
    c[1][2]=(1LL*a[1][1]*b[1][2]%mod+1LL*a[1][2]*b[2][2]%mod+1LL*a[1][3]*b[3][2]%mod)%mod;
    c[1][3]=(1LL*a[1][1]*b[1][3]%mod+1LL*a[1][2]*b[2][3]%mod+1LL*a[1][3]*b[3][3]%mod)%mod;
    c[2][1]=(1LL*a[2][1]*b[1][1]%mod+1LL*a[2][2]*b[2][1]%mod+1LL*a[2][3]*b[3][1]%mod)%mod;
    c[2][2]=(1LL*a[2][1]*b[1][2]%mod+1LL*a[2][2]*b[2][2]%mod+1LL*a[2][3]*b[3][2]%mod)%mod;
    c[2][3]=(1LL*a[2][1]*b[1][3]%mod+1LL*a[2][2]*b[2][3]%mod+1LL*a[2][3]*b[3][3]%mod)%mod;
    c[3][1]=(1LL*a[3][1]*b[1][1]%mod+1LL*a[3][2]*b[2][1]%mod+1LL*a[3][3]*b[3][1]%mod)%mod;
    c[3][2]=(1LL*a[3][1]*b[1][2]%mod+1LL*a[3][2]*b[2][2]%mod+1LL*a[3][3]*b[3][2]%mod)%mod;
    c[3][3]=(1LL*a[3][1]*b[1][3]%mod+1LL*a[3][2]*b[2][3]%mod+1LL*a[3][3]*b[3][3]%mod)%mod;
        for(i=1;i<=3;++i){
            for(j=1;j<=3;++j)
                a[i][j]=c[i][j];
        }

}

void alab(ull n){
    int i,j;
    ull rez[5][5];
    reset(rez);
    rez[1][1]=rez[2][2]=rez[3][3]=1;

   while( n>0 ){
        if(n%2) {
                inm(rez,b);
                --n;
        }
        inm(b,b);
        n = n/2;
    }
    for(i=1;i<=3;++i){
            for(j=1;j<=3;++j){
                b[i][j]=rez[i][j];}
        }

}

int main()
{
    in>>dco;
    while(dco--){
        reset(a);
        reset(b);
        in>>x>>y>>z;
        in>>A>>B>>C;
        in>>n;

        b[1][3]=C;
        b[2][1]=b[3][2]=1;
        b[2][3]=B;
        b[3][3]=A;
        a[1][1]=x;
        a[1][2]=y;
        a[1][3]=z;
        //out<<x<<' '<<y<<' '<<z<<' '<<A<<' '<<B<<' '<<C<<' '<<n<<' ';
        alab(n-2);
        inm(a,b);
        out<<a[1][3]%mod<<'\n';

    }
    return 0;
}