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

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], sol[5];
int n, ans;

void lgput(int mp[5][5], 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(mp, 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[k][j] * mpa[i][k];
                    mp[i][j] = mp[i][j] % mod;
                }
            }
    }
    if(p % 2 == 1)
    {
        lgput(mp, 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[k][j] * mpi[i][k];
                    mp[i][j] = mp[i][j] % mod;
                }
            }
    }
}

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

int main()
{
    int teste;
    fin >> teste;
    while(teste--)
        solve();
    return 0;
}