#include<fstream>
#define N  666013

using namespace std;
int main()
{
    int x,y,z,a,b,c,n,t,mat[4][4],rez[4][4],i,rezultatul,aux[4][4];
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    f>>t;
    for(i=1;i<=t;i++)
    {f>>x>>y>>z>>a>>b>>c>>n;
    n=n-3;
    mat[1][1]=x;mat[1][2]=y;mat[1][3]=z;
    mat[2][1]=1;mat[2][2]=0;mat[2][3]=0;
    mat[3][1]=0;mat[3][2]=1;mat[3][3]=0;
    
    
        rez[1][1]=x;rez[1][2]=y;rez[1][3]=z;
    rez[2][1]=1;rez[2][2]=0;rez[2][3]=0;
    rez[3][1]=0;rez[3][2]=1;rez[3][3]=0;
    
    while(n>0)
    {
              if (n%2)
              {  rez[1][1]=mat[1][1]*rez[1][1]+mat[1][2]*rez[2][1]+mat[1][3]*rez[3][1];
                  rez[1][2]=mat[1][1]*rez[1][2]+mat[1][2]*rez[2][2]+mat[1][3]*rez[3][2];
                  rez[1][3]=mat[1][1]*rez[1][3]+mat[1][2]*rez[2][3]+mat[1][3]*rez[3][3];
                  
                   rez[2][1]=mat[2][1]*rez[1][1]+mat[2][2]*rez[2][1]+mat[2][3]*rez[3][1];
                  rez[2][2]=mat[2][1]*rez[1][2]+mat[2][2]*rez[2][2]+mat[2][3]*rez[3][2];
                  rez[2][3]=mat[2][1]*rez[1][3]+mat[2][2]*rez[2][3]+mat[2][3]*rez[3][3];
                  
                   rez[3][1]=mat[3][1]*rez[1][1]+mat[3][2]*rez[2][1]+mat[3][3]*rez[3][1];
                  rez[3][2]=mat[3][1]*rez[1][2]+mat[3][2]*rez[2][2]+mat[3][3]*rez[3][2];
                  rez[3][3]=mat[3][1]*rez[1][3]+mat[3][2]*rez[2][3]+mat[3][3]*rez[3][3];
                  }
        //mat=mat*mT          
          aux[1][1]=mat[1][1]*mat[1][1]+mat[1][2]*mat[2][1]+mat[1][3]*mat[3][1];
                  aux[1][2]=mat[1][1]*mat[1][2]+mat[1][2]*mat[2][2]+mat[1][3]*mat[3][2];
                  aux[1][3]=mat[1][1]*mat[1][3]+mat[1][2]*mat[2][3]+mat[1][3]*mat[3][3];
                  
                   aux[2][1]=mat[2][1]*mat[1][1]+mat[2][2]*mat[2][1]+mat[2][3]*mat[3][1];
                  aux[2][2]=mat[2][1]*mat[1][2]+mat[2][2]*mat[2][2]+mat[2][3]*mat[3][2];
                  aux[2][3]=mat[2][1]*mat[1][3]+mat[2][2]*mat[2][3]+mat[2][3]*mat[3][3];
                  
                   aux[3][1]=mat[3][1]*mat[1][1]+mat[3][2]*mat[2][1]+mat[3][3]*mat[3][1];
                  aux[3][2]=mat[3][1]*mat[1][2]+mat[3][2]*mat[2][2]+mat[3][3]*mat[3][2];
                  aux[3][3]=mat[3][1]*mat[1][3]+mat[3][2]*mat[2][3]+mat[3][3]*mat[3][3];
                  
                  int j,k;
                  for(j=1;j<=3;j++)
                    for(k=1;k<=3;k++)  mat[j][k]=aux[j][k];
                  
                  n=n/2;
                  
                  }
                  
        rezultatul=(rez[1][1]*c+rez[1][2]*b+rez[1][3]*a)%N;
        g<<rezultatul<<endl;
        }
        
        
        
        return 0;}