#include <iostream>
#include <fstream>
#include <cstring>
#include <cassert>

using namespace std;

template <typename T>
struct matrix{
    T**  a;

    int l, c;

    matrix(int l = 0, int c = 0)
    {
        this->l = l;
        this->c = c;

        a = new T*[l];
        for (int i = 0; i < l; ++i)
            a[i] = new T[c];
    }

    matrix(const matrix& other)
    {
        a = new T*[l];
        for (int i = 0; i < l; ++i)
            a[i] = new T[c];

        this->l = other.l;
        this->c = other.c;

        for (int i = 0; i < l; ++i)
            for (int j = 0; j < c; j++)
                a[i][j] = other.a[i][j];
    }

    ~matrix()
    {
        for (int i = 0; i < l; ++i)
            delete[] a[i];
        delete[] a;
    }

    matrix& operator =(const matrix& other)
    {
        a = new T*[l];
        for (int i = 0; i < l; ++i)
            a[i] = new T[c];

        this->l = other.l;
        this->c = other.c;

        for (int i = 0; i < l; ++i)
            for (int j = 0; j < c; j++)
                a[i][j] = other.a[i][j];

        return *this;
    }

    matrix operator *(const matrix& other)
    {
        if(this->c != other.l)
        {
            cerr << "Could not multiply\n";
            assert(false);
        }

        matrix m(this->l, other.c);

        for(int i = 0; i < this->l; i++)
        {
            for(int j = 0; j < other.c; j++)
            {
                m.a[i][j] = 0;
                for(int k = 0; k < other.l; k++)
                    m.a[i][j]+=this->a[i][k]*other.a[k][j];
            }
        }
        return m;
    }

    matrix operator ^(const long int exp)
    {
        if(exp == 1)
            return *this;
        else
        if(exp == 2)
            return (*this)*(*this);
        else
        if(exp%2==1)
        {
            return ((*this)^(exp-1))*(*this);
        }
        else
        {
            matrix tmp = (*this)^(exp/2);
            return tmp*tmp;
        }
    }
};

int t;
matrix<unsigned long long int> v(1,3);
matrix<unsigned long long int> m(3,3);
unsigned long int n;

int main()
{
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");

    f >> t;
    for(int i = 0; i < t; i++)
    {
        m.a[0][0] = 0; m.a[0][1] = 0; m.a[0][2] = 0;
        m.a[1][0] = 1; m.a[1][1] = 0; m.a[1][2] = 0;
        m.a[2][0] = 0; m.a[2][1] = 1; m.a[2][2] = 0;

        f >> v.a[0][0] >> v.a[0][1] >> v.a[0][2];
        f >> m.a[2][2] >> m.a[1][2] >> m.a[0][2];
        f >> n;

        if(n == 3)
        {
            g << v.a[0][2]%666013 << '\n';
            continue;
        }

        m=m^(n-2);
        v=v*m;
        g << v.a[0][2]%666013 << '\n';
    }

    return 0;
}