#include <fstream>
#include <cstring>
#define MOD 666013
using namespace std;

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

int main()
{
    int n, q;
    long long sol[1][3], m[3][3], aux[3][3], aux1[3][3];
    fin>>q;
    while(q--)
    {
        fin>>sol[0][0]>>sol[0][1]>>sol[0][2]>>m[2][2]>>m[1][2]>>m[0][2]>>n;
        n=n-2;
        m[0][0]=0;
        m[0][1]=0;
        m[1][0]=1;
        m[1][1]=0;
        m[2][0]=0;
        m[2][1]=1;
        for(int i=1; i<=n; i<<=1)
        {
            if(n&i)
            {
                memcpy(aux, sol, sizeof sol);
                sol[0][0]=((aux[0][0]*m[0][0])%MOD+(aux[0][1]*m[1][0])%MOD+(aux[0][2]*m[2][0])%MOD)%MOD;
                sol[0][1]=((aux[0][0]*m[0][1])%MOD+(aux[0][1]*m[1][1])%MOD+(aux[0][2]*m[2][1])%MOD)%MOD;
                sol[0][2]=((aux[0][0]*m[0][2])%MOD+(aux[0][1]*m[1][2])%MOD+(aux[0][2]*m[2][2])%MOD)%MOD;
            }
            memcpy(aux, m, sizeof m);
            memcpy(aux1, m, sizeof m);
            m[0][0]=((aux[0][0]*aux1[0][0])%MOD+(aux[0][1]*aux1[1][0])%MOD+(aux[0][2]*aux1[2][0])%MOD)%MOD;
            m[0][1]=((aux[0][0]*aux1[0][1])%MOD+(aux[0][1]*aux1[1][1])%MOD+(aux[0][2]*aux1[2][1])%MOD)%MOD;
            m[0][2]=((aux[0][0]*aux1[0][2])%MOD+(aux[0][1]*aux1[1][2])%MOD+(aux[0][2]*aux1[2][2])%MOD)%MOD;
            m[1][0]=((aux[1][0]*aux1[0][0])%MOD+(aux[1][1]*aux1[1][0])%MOD+(aux[1][2]*aux1[2][0])%MOD)%MOD;
            m[1][1]=((aux[1][0]*aux1[0][1])%MOD+(aux[1][1]*aux1[1][1])%MOD+(aux[1][2]*aux1[2][1])%MOD)%MOD;
            m[1][2]=((aux[1][0]*aux1[0][2])%MOD+(aux[1][1]*aux1[1][2])%MOD+(aux[1][2]*aux1[2][2])%MOD)%MOD;
            m[2][0]=((aux[2][0]*aux1[0][0])%MOD+(aux[2][1]*aux1[1][0])%MOD+(aux[2][2]*aux1[2][0])%MOD)%MOD;
            m[2][1]=((aux[2][0]*aux1[0][1])%MOD+(aux[2][1]*aux1[1][1])%MOD+(aux[2][2]*aux1[2][1])%MOD)%MOD;
            m[2][2]=((aux[2][0]*aux1[0][2])%MOD+(aux[2][1]*aux1[1][2])%MOD+(aux[2][2]*aux1[2][2])%MOD)%MOD;
        }
        fout<<sol[0][2]<<'\n';
    }
    return 0;
}