#include <iostream>
#include <fstream>
#define mod 666013

using namespace std;

ifstream f("iepuri.in");
ofstream g("iepuri.out");


void init(long long M[4][4])
{
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            M[i][j]=0;
}
void afis(long long M[4][4])
{
    for(int i=1; i<=3; i++)
    {
        for(int j=1; j<=3; j++)
            cout<<M[i][j]<<" ";
        cout<<"\n";
    }
}
void calc_el(long long A[4][4],long long B[4][4])
{
    long long R[4][4];
    init(R);
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            for(int k=1; k<=3; k++)
                R[i][j]+=((1LL*A[i][k])%mod*(1LL*B[k][j])%mod)%mod;
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            B[i][j]=R[i][j];
}
void putere(long long A[4][4],long long  C[4][4], long long n)
{
    init(C);
    for(int i=1; i<=3; i++)
        for(int j=1; j<=3; j++)
            C[i][j]=(i==j);
    while(n)
    {
        if(n & 1)
            calc_el(A,C);
        n=n>>1;https:
        calc_el(A,A);
    }
}
int main()
{
    long long mat[4][4],C[4][4];
    int T,x,y,z,a,b,c,N;
    f>>T;
    while(T--)
    {
        f>>x>>y>>z>>a>>b>>c>>N;
        long long ans=0;
        mat[1][1]=a;
        mat[1][2]=b;
        mat[1][3]=c;
        mat[2][1]=mat[3][2]=1;
        mat[2][2]=mat[2][3]=mat[3][1]=mat[3][3]=0;
        //afis(mat);
        putere(mat,C,N-2);
        ans=((1LL*(C[1][1]%mod)*(z%mod))%mod+(1LL*(C[1][2]%mod)*(y%mod))%mod+(1LL*(C[1][3]%mod)*(x%mod)))%mod;
        g<<ans<<"\n";
        //afis(C);
    }
    return 0;
}