#include <stdio.h>

int main()
{
    FILE* fin = fopen("iepuri.in", "r");
    FILE* fout = fopen("iepuri.out", "w");
    
    int T, X, Y, Z, A, B, C, N;
    fscanf(fin, "%d", &T);
    
    long long int a[4];
    for (int i = 0; i < T; i++)
    {
        fscanf(fin, "%d %d %d %d %d %d %d", &X, &Y, &Z, &A, &B, &C, &N);
        
        a[0] = X;
        a[1] = Y;
        a[2] = Z;
        for (int i = 3; i <= N; i++)
        {
            a[3] = A*a[2] + B*a[1] + C*a[0];
            a[0] = a[1];
            a[1] = a[2];
            a[2] = a[3];
            
            if (a[3] >= 666013 && a[2] >= 666013 && a[1] >= 666013 && a[0] >= 666013)
            {
                     a[3] %= 666013;
                     a[2] %= 666013;
                     a[1] %= 666013;
                     a[0] %= 666013;
            }
            
        }
        
        if (N < 3)
           fprintf(fout, "%d\n", a[N]);
        else
            fprintf(fout, "%d\n", a[3] % 666013);        
    }
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}