#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <ctime>


using namespace std;
;

int v[100010],i,j,n,m,k,T,A,B,C,x,y,z;
int M = 666013;
struct matrix {
  int m[3][3];
  matrix operator * (matrix b)
  {
     matrix c = matrix();
     for (int i = 0; i < 3; ++i)
       for (int j = 0; j < 3; ++j)
         for (int k = 0; k < 3; ++k)
           c.m[i][j] = (c.m[i][j] + 1LL * m[i][k] * b.m[k][j]) % M;
     return c;
  }
};

matrix a,I,b;

ifstream cin("iepuri.in");
ofstream cout("iepuri.out");

matrix put( matrix x, int p )
{
    if( p == 0 )
        return I;
    if( p == 1 )
        return b;
    matrix aux = put( x , p / 2 );
    aux = aux * aux;
    if( p % 2 == 1 )
        aux = aux * x;
    return  aux;
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>x>>y>>z>>A>>B>>C>>n;
        for( i = 1 ; i <= 3 ; i++ )
        for( j = 1 ; j <= 3 ; j++ )
            a.m[ i ][ j ] = b.m[ i ][ j ] = 0;
        a.m[ 0 ][ 0 ] = x;
        a.m[ 0 ][ 1 ] = y;
        a.m[ 0 ][ 2 ] = z;

        b.m[ 1 ][ 0 ] = 1;
        b.m[ 2 ][ 1 ] = 1;
        b.m[ 0 ][ 2 ] = C;
        b.m[ 1 ][ 2 ] = B;
        b.m[ 2 ][ 2 ] = A;

        b = put( b , n - 2 );
        a = a * b;
        cout<<a.m[ 0 ][ 2 ]<<'\n';
    }
    return 0;
}