#include <fstream>
#include <cstring>
 
#define In "iepuri.in"
#define Out "iepuri.out"
#define MOD 666013
 
using namespace std;
 
long long M[5][5],A[5][5],sol[5];
 
inline void Inm(long long C[][5],long long A[][5],long long B[][5])
{
    long long i, j, k;
    for(i = 1;i <= 3; ++i)
        for(j = 1;j <= 3; ++j)
            for(k = 1 ; k <= 3; ++k)
                C[i][j] = (1LL*C[i][j]+1LL*A[i][k]*B[k][j])%MOD;
}
 
inline void PowLog(long long k)
{
    long long aux[5][5];
    while(k)
    {
        if(k&1)
        {
            memset(aux,0,sizeof(aux));
            Inm(aux,A,M);
            memcpy(A,aux,sizeof(aux));
        }
        k >>= 1;
        memset(aux,0,sizeof(aux));
        Inm(aux,M,M);
        memcpy(M,aux,sizeof(aux));
    }
}
int main()
{
    ifstream f(In);
    ofstream g(Out);
    long long n,T, i;
    for(f>> T; T; --T)
    {
        memset(M,0,sizeof(M));
        memset(A,0,sizeof(A));
        A[1][1] = A[2][2] = A[3][3] = 1;
        f >> sol[0] >> sol[1] >> sol[2] >> M[3][3] >> M[3][2] >> M[3][1] >> n;
        M[1][2] = M[2][3] = 1;
        PowLog(n-2);
        sol[3] = 0;
        for(i = 1 ;i <= 3; ++i)
            sol[3] =( 1LL*sol[3]+A[3][i]*sol[i-1])%MOD;
        g<<sol[3]<<"\n";
    }
    f.close();
    g.close();
    return 0;
}