#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ifstream f("iepuri.in");
ofstream g("iepuri.out");

const int MOD = 666013;
const ll NMAX = 2e9;

int A,B,C,X,Y,Z,mat[4][4],ans[4],T;
ll N;

void create(){
              //ifstream cin("iepuri.in");
              f>>X>>Y>>Z>>A>>B>>C>>N;
              ans[1]=Z;
              ans[2]=Y;
              ans[3]=X;
              mat[1][1]=A;
              mat[2][1]=B;
              mat[3][1]=C;
              mat[1][2]=1;
              mat[1][3]=0;
              mat[2][2]=0;
              mat[2][3]=1;
              mat[3][2]=0;
              mat[3][3]=0;
             }

void inmMat(int a[4][4],int b[4][4]){
                                      int c[4][4];
                                      for(int i=1;i<=3;++i)
                                         for(int j=1;j<=3;++j){
                                                                c[i][j]=0;
                                                                for(int k=1;k<=3;++k)
                                                                c[i][j]+=(1LL*a[i][k]*b[k][j])%MOD;
                                                              }

                                      for(int i=1;i<=3;++i)
                                         for(int j=1;j<=3;++j)a[i][j]=c[i][j];
                                    }

void matPow(int a[4][4],ll n){
                               int aux[4][4];
                               for(int i=1;i<=3;++i)
                                  for(int j=1;j<=3;++j)
                                if(i==j)aux[i][j]=1;
                                else aux[i][j]=0;
                                while(n){
                                           if(n%2)inmMat(aux,a);
                                           inmMat(a,a);
                                           n/=2;
                                          }
                              for(int i=1;i<=3;++i)
                                  for(int j=1;j<=3;++j) a[i][j]=aux[i][j];
                             }

void inmMatVct(int a[4][4],int b[4]){
                                      int c[4];
                                      for(int i=1;i<=3;++i){
                                                            c[i]=0;
                                                            for(int j=1;j<=3;++j)
                                                            c[i]+=(1LL*a[j][i]*b[j])%MOD;
                                                           }

                                      for(int i=1;i<=3;++i)b[i]=c[i];
                                    }

int main(){
            //ifstream cin("iepuri.in");
          //  ofstream cout("iepuri.out");
            f>>T;
            while(T--){
                       create();
                       matPow(mat,N-2);
                       inmMatVct(mat,ans);
                       g<<ans[1]<<'\n';
                      }
            return 0;
          }