#include <iostream>
#include <fstream>

using namespace std;

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

const int mod = 666013;
int mpa[5][5], mp[5][5], mpi[5][5], mi[2][5], mr[2][5];
int n, ans;

void lgput(int p)
{
    if(p == 1)
    {
        for(int i = 1; i <= 3; i++)
            for(int j = 1; j <= 3; j++)
                mp[i][j] = mpi[i][j];
        return;
    }
    if(p % 2 == 0)
    {
        lgput(p/2);
        for(int i = 1; i <= 3; i++)
            for(int j = 1; j <= 3; j++)
                mpa[i][j] = mp[i][j];
        for(int i = 1; i <= 3; i++)
            for(int j = 1; j <= 3; j++)
            {
                mp[i][j] = 0;
                for(int k = 1; k <= 3; k++)
                {
                    mp[i][j] += mpa[i][k] * mpa[k][j];
                    mp[i][j] = mp[i][j] % mod;
                }
            }
    }
    if(p % 2 == 1)
    {
        lgput(p - 1);
        for(int i = 1; i <= 3; i++)
            for(int j = 1; j <= 3; j++)
                mpa[i][j] = mp[i][j];
        for(int i = 1; i <= 3; i++)
            for(int j = 1; j <= 3; j++)
            {
                mp[i][j] = 0;
                for(int k = 1; k <= 3; k++)
                {
                    mp[i][j] += mpa[i][k] * mpi[k][j];
                    mp[i][j] = mp[i][j] % mod;
                }
            }
    }
}

void solve()
{
    for(int i = 1; i <= 3; i++)
        fin >> mi[1][i];
    for(int i = 3; i >= 1; i--)
        fin >> mpi[i][3];
    fin >> n;
    ans = 0;
    lgput(n-2);
    for(int i = 1; i <= 3; i++)
    {
        ans += mi[1][i]*mp[i][3];
        ans = ans % mod;
    }
    fout << ans << '\n';
}

int main()
{
    int teste;
    fin >> teste;
    mpi[2][1] = 1;
    mpi[3][2] = 1;
    while(teste--)
        solve();
    return 0;
}