#include<iostream>
#include<fstream>
#include<cmath>
using namespace std;

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

long long x, y, z, a, b, c, n, t, n1, z2, y2, x2;
long long A[4][4], B[4][4];
bool v[32];

void citire()
{
    fin>>x>>y>>z>>a>>b>>c>>n;
}

void matric()
{
    A[1][1] = a;
    A[1][2] = b;
    A[1][3] = c;
    A[2][1] = 1;
    A[2][2] = 0;
    A[2][3] = 0;
    A[3][1] = 0;
    A[3][2] = 1;
    A[3][3] = 0;
}

void patrmatric()
{
    B[1][1] = A[1][1] * A[1][1] + A[1][2] * A[2][1] + A[1][3] * A[3][1];
    B[1][2] = A[1][1] * A[1][2] + A[1][2] * A[2][2] + A[1][3] * A[3][2];
    B[1][3] = A[1][1] * A[1][3] + A[1][2] * A[2][3] + A[1][3] * A[3][3];
    B[2][1] = A[2][1] * A[1][1] + A[2][2] * A[2][1] + A[2][3] * A[3][1];
    B[2][2] = A[2][1] * A[1][2] + A[2][2] * A[2][2] + A[2][3] * A[3][2];
    B[2][3] = A[2][1] * A[1][3] + A[2][2] * A[2][3] + A[2][3] * A[3][3];
    B[3][1] = A[3][1] * A[1][1] + A[3][2] * A[2][1] + A[3][3] * A[3][1];
    B[3][2] = A[3][1] * A[1][2] + A[3][2] * A[2][2] + A[3][3] * A[3][2];
    B[3][3] = A[3][1] * A[1][3] + A[3][2] * A[2][3] + A[3][3] * A[3][3];

    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j) A[i][j] = B[i][j] % 666013;
}

void binar()
{
    long long p1 = n;
    long long x = powl(2, 32);
    for(int i = 32; i >= 0; --i)
    {
        v[i] = 0;
        if(p1 >= x)
        {
            v[i] = 1;
            p1 -= x;
        }
        x /= 2;
    }
}

int main()
{
    fin>>t;

    while(t)
    {
        citire();
        if(n == 0) fout<<x;
        else if(n == 1) fout<<y;
        else if(n == 2) fout<<z;
        else
        {
            n -= 2;
            matric();
            binar();
            for(int i = 0; i <= 32; ++i)
            {
                if(v[i])
                {
                    z2 = A[1][1] * z + A[1][2] * y + A[1][3] * x;
                    y2 = A[2][1] * z + A[2][2] * y + A[2][3] * x;
                    x2 = A[3][1] * z + A[3][2] * y + A[3][3] * x;
                    z = z2 % 666013;
                    y = y2 % 666013;
                    x = x2 % 666013;
                }
                patrmatric();
            }
            fout<<z<<"\n";
        }
        --t;
    }
}