#include <iostream>
#include <fstream>

using namespace std;

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

int main()
{
    int nr,A,B,C,N;
    fin >> nr;
    int v[8];
    for (int i = 1; i <= nr; i++)
    {
        for (int j = 0; j <6; j++)
        {
            fin >> v[j];
        }
        A = v[3];
        B = v[4];
        C = v[5];
        for (int k = 3; k <6; k++)
        {
           
            v[k] = A * v[k - 1] + B * v[k - 2] + C * v[k - 3];
        }
        fin >> N;
        int R = v[N] % 666013;
        fout << R << endl;

       

    }
    return 0;
}