#include <iostream>
#include <fstream>

using namespace std;
ifstream si("iepuri.in");
ofstream so("iepuri.out");
int aux[5][5],sol[5][5],v[5][5];
const int MOD=666013;
int main()
{
    int q;
    si>>q;
    int n,i,j,k;
    long long p;
    while(q--)
    {
        si>>sol[1][1]>>sol[1][2]>>sol[1][3]>>v[3][3]>>v[2][3]>>v[1][3]>>n;
        v[2][1]=v[3][2]=1;
        n-=2;
        for(p=1;p<=n;p<<=1)
        {
            if(n&p)
            {

                for(i=1;i<4;++i)
                {
                    for(j=1;j<4;++j)
                        aux[i][j]=0;
                }
                for(i=1;i<4;++i)
                {
                    for(j=1;j<4;++j)
                    {
                        for(k=1;k<4;++k)
                        {
                            aux[i][k]=(aux[i][k]+1LL*sol[i][j]*v[j][k])%MOD;
                        }
                    }
                }

                for(i=1;i<4;++i)
                {
                    for(j=1;j<4;++j)
                        sol[i][j]=aux[i][j];
                }
            }
            for(i=1;i<4;++i)
            {
                for(j=1;j<4;++j)
                    aux[i][j]=0;
            }
            for(i=1;i<4;++i)
            {
                for(j=1;j<4;++j)
                {
                    for(k=1;k<4;++k)
                    {
                        aux[i][k]=(aux[i][k]+1LL*v[i][j]*v[j][k])%MOD;
                    }
                }
            }

            for(i=1;i<4;++i)
            {
                for(j=1;j<4;++j)
                {
                  //  cout<<v[i][j]<<' ';
                    v[i][j]=aux[i][j];
                }
                //cout<<'\n';
            }
            //cout<<'\n';

        }
        so<<sol[1][3]<<'\n';

        for(i=1;i<4;++i)
        {
            for(j=1;j<4;++j)
            {
                sol[i][j]=0;
                v[i][j]=0;
            }
        }
    }
    return 0;
}