//40 puncte
#include <fstream>
using namespace std;

#define in "iepuri.in"
#define out "iepuri.out"
#define NMAX 2000001

typedef long long int LLI;
LLI iep[NMAX], T;
LLI f_day, s_day, t_day, c1, c2, c3, last;
LLI n;

void Read();
void Dinamic();
void Write();

FILE *fout = fopen( out, "w" );

int main()
{
    Read();
     
    fclose( fout );
    return 0;
}
void Read()
{
    FILE *fin = fopen( in, "r" );
    int i;
    fscanf( fin, "%d", &T );
    for ( i = 1; i <= T; ++i )
    {
        fscanf( fin, "%lld%lld%lld%lld%lld%lld%lld", &f_day, &s_day, &t_day, &c1, &c2, &c3, &n );
        Dinamic();
        if ( last > 666013 ) 
        {
             last -= 666013;
        }
        fprintf( fout, "%lld\n", last );
    }
    fclose( fin );
}

void Dinamic()
{
     LLI i;
     /*memset( iep, 0, sizeof( iep ) );
     iep[0] = f_day;
     iep[1] = s_day;
     iep[2] = t_day;*/
     
     /*for ( i = 3; i <= n; ++i )
     {
         iep[i] = (c1*iep[i-1]) + (c2*iep[i-2]) + (c3*iep[i-3]);
         iep[i] = iep[i]%666013;
     }*/
     last = f_day * c3 + s_day * c2 + t_day * c1;
     for ( i = 3; i <= n; ++i )
     {
         last = f_day * c3 + s_day * c2 + t_day * c1;
         //last = last%666013;
         if ( last > 666013 ) 
         {
              last -= 666013;
         }
         f_day = s_day;
         s_day = t_day;
         t_day = last;
     }
}