// Problema Iepuri

#include <stdio.h>
#define  MOD      666013

int main()
{
    int T;
    long N, s, X, Y, Z, A, B, C;
    freopen( "iepuri.in", "rt", stdin );
             scanf( "%d", &T );
    freopen( "iepuri.out", "wt", stdout );
             while( T > 0 )
             {
                    T--;
             scanf( "%ld %ld %ld %ld %ld %ld %ld", &X, &Y, &Z, &A, &B, &C, &N );
             s = Z*A + Y*B + X*C;
             while( N > 3 )
             {
                    N--;
                    X = Y;
                    Y = Z;
                    Z = s%MOD;
                    s = Z*A + Y*B + X*C;                     
             }
             printf( "%ld\n", s%MOD );
             }
    fclose( stdin );
    fclose( stdout );    
    return 0;    
}