#include <fstream>
#include <cstring>
using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

struct matrix
{
    int m[3][3];
    matrix()
    {
        memset( m , 0 , sizeof( m ) );
    }

    matrix operator * ( matrix b )
    {
        matrix out = matrix();
        for( int i = 0 ; i < 3 ; i++ )
        for( int k = 0 ; k < 3 ; k++ )
        for( int j = 0 ; j < 3 ; j++ )
            out.m[ i ][ j ] = ( out.m[ i ][ j ] + m[ i ][ k ] * b.m[ k ][ j ] ) % 666013;
    return out;
    }
};

matrix unit;

matrix modPow( matrix x, int n )
{
    if( n == 0 )
        return unit;

    matrix half = modPow( x , n / 2 );
    half = half * half;

    if( n % 2 )
        half = half * x;

return half;
}

int main()
{
    unit.m[ 0 ][ 0 ] = unit.m[ 1 ][ 1 ] = unit.m[ 2 ][ 2 ] = 1;

    int x,y,z,a,b,c,n,t;

    fin>>t;

    while( t-- )
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        matrix A = matrix();
        matrix B = matrix();
        A.m[ 0 ][ 0 ] = x;
        A.m[ 0 ][ 1 ] = y;
        A.m[ 0 ][ 2 ] = z;

        B.m[ 0 ][ 0 ] = 0;
        B.m[ 1 ][ 0 ] = 1;
        B.m[ 2 ][ 0 ] = 0;
        B.m[ 0 ][ 1 ] = 0;
        B.m[ 1 ][ 1 ] = 0;
        B.m[ 2 ][ 1 ] = 1;
        B.m[ 0 ][ 2 ] = c;
        B.m[ 1 ][ 2 ] = b;
        B.m[ 2 ][ 2 ] = a;

        B = modPow( B , n - 2 );
        A = A * B;
        fout<<A.m[ 0 ][ 2 ]<<'\n';
    }


return 0;
}