#include<fstream>
using namespace std;
 
# define MOD 666013
 
ifstream f("iepuri.in");
ofstream g("iepuri.out");
 
long long N,M[3][3],M_N[3][3],T,I[3],A[3][3];
 
void inmulteste()
{
    long long i,j,k,s;
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
        {
            s=0;
            for(k=0;k<3;++k)
                s+=A[i][k]*A[k][j], s%=MOD;
            M_N[i][j]=s;
         }
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            A[i][j]=M_N[i][j];
}
void inmultestem()
{
    long long i,j,k,s;
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
        {
           s=0;
            for(k=0;k<3;++k)
                s+=A[i][k]*M[k][j], s%=MOD;
            M_N[i][j]=s;
        }
    for(i=0;i<3;++i)
        for(j=0;j<3;++j)
            A[i][j]=M_N[i][j];
}
void putere(int n)
{
    if(n<=1)
        return;
  putere(n/2);
    inmulteste();
    if(n&1)
        inmultestem();
}
int main()
{
    M[0][1]=1, M[1][2]=1;
    f>>T;
    long long i,j,s;
    for(;T;--T)
    {
        f>>I[0]>>I[1]>>I[2]>>M[2][2]>>M[2][1]>>M[2][0]>>N;
        N-=2;
        for(i=0;i<3;++i)
            for(j=0;j<3;++j)
                A[i][j]=M[i][j];
        putere(N);
        s=0;
        for(i=0;i<3;++i)
           s+=M_N[2][i]*I[i], s%=MOD;
        g<<s<<'\n';
    }
}