#include <bits/stdc++.h>

using namespace std;

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

const int Nmax=2000000, mod=666013;
int t,x,y,z,a,b,c,n;
int dp[5];

void solve()
{
    dp[4]=((a*dp[3]%mod+b*dp[2]%mod)%mod+c*dp[1]%mod)%mod;
    dp[1]=dp[2];
    dp[2]=dp[3];
    dp[3]=dp[4];
}

int main()
{
    in>>t;
    for(int i=1;i<=t;++i)
    {
        in>>x>>y>>z>>a>>b>>c>>n;
        dp[1]=x;
        dp[2]=y;
        dp[3]=z;
        for(int j=3;j<=n;++j)
            solve();
        out<<dp[4]<<endl;
    }

    return 0;
}