#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define MODULO 666013;

FILE *fin, *fout;
int iepuri[5];
int t, x, y, z, a, b, c;
long n;
long zi;
long r;

inline void citeste(void);
inline void scrie(long nr);     
void rezolva(void);
inline void initializeaza(void);
  
int main()
{
    fin = fopen("iepuri.in", "r");
    fout = fopen("iepuri.out", "w");
    fscanf(fin, "%d", &t);
    for (int i = 1; i <= t; i++)
    {
        citeste();
        initializeaza();
        rezolva();
        scrie(iepuri[3]);
    }
    fclose(fin); fclose(fout);
    return 0;
}

void rezolva()
{
       for (int i = zi; i <= n; i++)
       {           
           iepuri[3] = (a * iepuri[2]) + (b * iepuri[1]) + (c * iepuri[0]);                   
           iepuri[0] = iepuri[1];
           iepuri[1] = iepuri[2];
           iepuri[2] = iepuri[3];
       }      
        iepuri[3] = iepuri[3] % MODULO;  
}

inline void initializeaza()
{
     zi = 3;
}

inline void citeste()
{
     //X Y Z A B C N
     fscanf(fin, "%d%d%d%d%d%d%d", &iepuri[0], &iepuri[1], &iepuri[2], &a, &b, &c, &n);
}

inline void scrie(long nr)
{  
     fprintf(fout, "%d\n", nr);
}