#include <bits/stdc++.h>

using namespace std;
ifstream fin ("iepuri.in");
ofstream fout ("iepuri.out");
const int mod=666013;
int d0[3][3],x,y,z;
void X(int a[][3],int b[][3])
{
    int r[3][3]={0};
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
            r[i][j]=(r[i][j]+1ll*a[i][k]*b[k][j]%mod)%mod;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            a[i][j]=r[i][j];
}
int power(int base[][3],int power)
{
    int r[3][3]={0};
    r[0][0]=r[1][1]=r[2][2]=1;
    while(power)
    {
        if(power%2)
            X(r,base);
        X(base,base);
        power/=2;
    }
    return (r[0][0]*z%mod+r[0][1]*y%mod+r[0][2]*x%mod)%mod;
}
void solve()
{
    int a,b,c,n;
    fin>>x>>y>>z>>a>>b>>c>>n;
    for(int i=1;i<3;i++)
        for(int j=0;j<3;j++)
            d0[i][j]=0;
    d0[1][0]=d0[2][1]=1;
    d0[0][0]=a,d0[0][1]=b,d0[0][2]=c;
    fout<<power(d0,n-2)<<'\n';
}
int main()
{
    int tc;
    fin>>tc;
    while(tc--)
        solve();
    return 0;
}