#include <bits/stdc++.h>
#define N 3
#define M 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
long long a[N][N],b[N][N],sol[N][N],n;
long long X,Y,Z,A,B,C,T;
void inmultire(long long a[N][N], long long b[N][N])
{
    int c[26][26],i,j,k;
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
        {
            c[i][j]=0;
            for(k=0; k<N; k++)
            {
                c[i][j]+=((a[i][k]%M)*(b[k][j]%M))%M;
                c[i][j]=c[i][j]%M;
            }
        }
    for(i=0; i<N; i++)
        for(j=0; j<N; j++) a[i][j]=c[i][j];
}
int main()
{
    f>>T;
    for(int k=1; k<=T; k++)
    {
        f>>X>>Y>>Z>>A>>B>>C>>n;
        a[0][0]=X;
        a[0][1]=Y;
        a[0][2]=Z;
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
                b[i][j]=0;
        }
        b[0][2]=C;
        b[1][2]=B;
        b[2][2]=A;
        b[1][0]=1;
        b[2][1]=1;
        if(n>=3)
        {for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
                if(i==j) sol[i][j]=1;
                else sol[i][j]=0;
        }
        while(n)
        {
            if(n%2==1) inmultire(sol,b),n--;
            else inmultire(b,b),n/=2;
        }
        inmultire(a,sol);
        g<<a[0][0]<<'\n';
        }
        else
            g<<a[0][n]<<'\n';
    }
    return 0;
}