#include <fstream>


#define MOD 666013


using namespace std;

ofstream fout("iepuri.out");

/*
          
void afis(long long M[][3])
           {int i, j;
            for(i=0; i<3; i++, fout<<'\n')
                for(j=0; j<3; j++)
                   fout<<M[i][j]<<" ";
            
            fout<<'\n';
           }  

*/

void mult (long long  A[][3], long long B[][3])
         {int i, j, k, s;
          long long C[3][3]; 
          for(i=0;i<3;i++)
              for(j=0, s=0;j<3;C[i][j]=s, j++, s=0)
                  for(k=0;k<3;k++)
                      s=(s+( (A[i][k] % MOD) * ( B[k][j] % MOD ) ) % MOD) % MOD;
          for(i=0;i<3;i++)
             for(j=0;j<3;j++)
                 A[i][j]=C[i][j];
         }
         
void mult2(long long M[][3] , long long A[][1] )
          {int i, j, s;
           long long C[3][1];
           for(i=0, s=0;i<3;C[i][0]=s, s=0 , i++)
                  for(j=0;j<3;j++)
                     s=(s+( (M[i][j] % MOD) * ( A[j][0] % MOD ) ) % MOD) % MOD;
           for(i=0;i<3;i++)
               A[i][0]=C[i][0];          
          }       
         
   
 void power(long long M[][3], int N)
         {int i, j;
          long long C[3][3];
          C[0][0]=C[1][1]=C[2][2]=1;
          C[0][1]=C[0][2]=C[1][0]=C[1][2]=C[2][0]=C[2][1]=0;          
          for(i= 1<< 30; i>0; i>>=1)
             {mult(C,C); 
              if(N&i)
                  mult(C,M);
               
                  }
           for(i=0;i<3;i++)
               for(j=0;j<3;j++)
                  M[i][j]=C[i][j];       
                      
          }
      
                    
                              
           
int main(void)
       {int x, y, z, n, t;
        long long M[3][3];
        long long A[3][1];
        ifstream fin("iepuri.in");
        fin>>t;
        int i;
        for(i=1;i<=t;i++)                                        
            {fin>>A[0][0]>>A[1][0]>>A[2][0];
             M[0][0]=M[0][2]=M[1][0]=M[1][1]=0;
             M[0][1]=M[1][2]=1;
             fin>>M[2][2]>>M[2][1]>>M[2][0];
             fin>>n; 
             power(M, n);
             mult2(M, A);
             fout<<A[0][0]<<'\n';
            }
         fin.close();
         fout.close();
         
         
         return 0;
         }