#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cstring>

using namespace std;

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

#define ull unsigned long long int

#define MOD 666013
int mod(ull a, ull b)
{
    return ((a%MOD)*(b%MOD))%MOD;
}
struct M
{
public :
    ull a[3][3] ;

    M()
    {

    }

    M(ull b[3][3]){
        for(int i = 0 ; i < 3 ; i++)
        {
            for(int j = 0 ; j <3 ; j++)
            {
                a[i][j] = b[i][j];
            }

        }


    }

    M(const M &p)
    {
        for(int i = 0 ; i < 3 ; i++)
        {
            for(int j = 0 ; j <3 ; j++)
            {
                a[i][j] = p.a[i][j];
            }
        }
    }



    M operator *(const M& right)
    {
        struct M res;

        int lin = 3;
        int col = 3;
        for(int i = 0 ; i < lin ; i++)
        {
            for(int j = 0 ; j <col ; j++)
            {
                int aij = 0;
                for(int k = 0 ; k < col ; k++)
                {
                    aij =  (aij + mod(a[i][k],right.a[k][j]))%MOD;
                }
                res.a[i][j] = aij;
            }
        }

        return res;

    }
};


int rabbit(ull x, ull y, ull z,ull a,ull b, ull c, ull n)
{


    struct M base(new ull[3][3]
    { {a,b,c}, {1,0,0}, {0,1,0}
    });


    struct M res(new ull[3][3]
    { {1,0,0}, {0,1,0}, {0,0,1}
    });

    n -=2;

    while(n >0 )
    {

        if(n&1)
        {
            res = res*base;
        }

        base = base * base;
        n >>=1;
    }
    return ((mod(z,res.a[0][0])+ mod(y,res.a[0][1]))%MOD + mod(x,res.a[0][2]))%MOD;

}




int main ( )
{
    ull t,X, Y, Z, A,B,C,N;
    in>>t;

    while(t--)
    {
        in>>X>>Y>>Z>>A>>B>>C>>N;
        out<<rabbit(X,Y,Z,A,B,C,N)<<'\n';
    }

    return 0;
}