#include <fstream>
#define p 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
void Putere(int v[4][4],int k)
           {int i,j,v1[4][4],q;
            if(k>1)
            {for(i=1;i<=3;i++)
               for(j=1;j<=3;j++)
                  v1[i][j]=v[i][j];
             if(k%2==1){int v2[4][4];
                        for(i=1;i<=3;i++)
                           for(j=1;j<=3;j++)
                              v2[i][j]=v1[i][j];
                        Putere(v1,k-1);
                        for(i=1;i<=3;i++)
                           {for(j=1;j<=3;j++)
                               {for(q=1;q<=3;q++)
                                   {if(q==1){v[i][j]=0;}
                                     v[i][j]=(1LL*v[i][j]+1LL*v1[i][q]*v2[q][j]%p)%p;
                                   }
                               }
                           }
                       }
             else {for(i=1;i<=3;i++)
                           {for(j=1;j<=3;j++)
                               {for(q=1;q<=3;q++)
                                   {if(q==1){v[i][j]=0;}
                                   v[i][j]=(1LL*v[i][j]+1LL*v1[i][q]*v1[q][j]%p)%p;
                                   }
                               }
                           }
                   Putere(v,k/2);
                  }
            }
           }
int n,x,y,z,t,a,b,c,k,m[4][4];
int main()
{fin>>t;
 int i;
 for(i=1;i<=t;i++)
    {fin>>x>>y>>z>>a>>b>>c>>n;
     m[1][1]=m[1][2]=m[2][2]=m[3][1]=0;
     m[2][1]=m[3][2]=1;
     m[1][3]=c;m[2][3]=b;m[3][3]=a;
     Putere(m,n-2);
     fout<<(1LL*m[1][3]*x%p+1LL*m[2][3]*y%p+1LL*m[3][3]*z%p)%p<<"\n";
    }
}