#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

struct matrix
{
    long long m[3][3];
    void operator *= (const matrix &a)
    {
        int i, j, k;
        matrix c;
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
            {
                c.m[i][j] = 0; //initializarea;
                for(int k = 0; k < 3; k++)
                    c.m[i][j] += m[i][k] * a.m[k][j];
                c.m[i][j] %= MOD;
            }
        for(int i = 0; i < 3; i++)
            for(int j = 0; j < 3; j++)
                m[i][j] = c.m[i][j];
    }
};

matrix lg_put(matrix b, matrix rez, int exp)//ridicare la putere in timp logaritmic cu op pe biti
{
    for(int bit = 1; bit <= exp; bit <<= 1)
    {
        if(exp & bit)
            rez *= b; // rez = 1ll *
        b *= b; // b = 1ll * b * b % MOD
    }
    return rez;
}

int main()
{
    int t, a, b, c, x, y, z, n;
    fin >> t;
    for(int i = 1; i <= t; i++)
    {
        fin >> x >> y >> z >> a >> b >> c >> n;
        matrix baza = {0}, rez = {0};
        rez.m[0][0] = x; rez.m[0][1] = y; rez.m[0][2] = z;
        baza.m[1][0] = baza.m[2][1] = 1;
        baza.m[0][2] = c; baza.m[1][2] = b; baza.m[2][2] = a;

        //regula x(n-1) = a*x(n-1) + b*x(n-2) + c*x(n-3)
        rez = lg_put(baza,rez,n);
        fout<< rez.m[0][0]<<'\n';
    }
    /*for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                fout << rez.m[i][j];*/
    return 0;
}