#include <iostream>
#include <fstream>
#include <tuple>
#define int long long

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

const int MOD=666013;
int t,x,y,z,a,b,c,n;
tuple <int,int,int,int,int,int,int,int,int> sol;

tuple <int,int,int,int,int,int,int,int,int> inmultire(int a,int b,int c,int d,int e,int f,int g,int h,int i,int j,int k,int l,int m,int n,int o,int p,int q,int r)
{
    return {(a*j+b*m+c*p)%MOD,(a*k+b*n+c*q)%MOD,(a*l+b*o+c*r)%MOD,(d*j+e*m+f*p)%MOD,(d*k+e*n+f*q)%MOD,(d*l+e*o+f*r)%MOD,(g*j+h*m+i*p)%MOD,(g*k+h*n+i*q)%MOD,(g*l+h*o+i*r)%MOD};
}

tuple <int,int,int,int,int,int,int,int,int> putere(int p)
{
    if (p==1)
    return {0,0,c,1,0,b,0,1,a};

    if (p&1)
    {
        tuple <int,int,int,int,int,int,int,int,int> d=putere(p-1);
        return inmultire(0,0,c,1,0,b,0,1,a,get<0>(d),get<1>(d),get<2>(d),get<3>(d),get<4>(d),get<5>(d),get<6>(d),get<7>(d),get<8>(d));
    }

    tuple <int,int,int,int,int,int,int,int,int> d=putere(p>>1);
    return inmultire(get<0>(d),get<1>(d),get<2>(d),get<3>(d),get<4>(d),get<5>(d),get<6>(d),get<7>(d),get<8>(d),get<0>(d),get<1>(d),get<2>(d),get<3>(d),get<4>(d),get<5>(d),get<6>(d),get<7>(d),get<8>(d));
}

signed main()
{
    fin>>t;
    while (t)
    {
        fin>>x>>y>>z>>a>>b>>c>>n;
        sol=putere(n-2);

        fout<<(x*get<2>(sol)+y*get<5>(sol)+z*get<8>(sol))%MOD<<"\n";

        t--;
    }

    return 0;
}