#include <iostream>
#include <fstream>
#include <cstring>

#define mod 666013;

std::ifstream f ("iepuri.in");
std::ofstream t ("iepuri.out");

using namespace std;

const int dim=3;

struct matrix
{
    int v[dim][dim];
    matrix()
    {
        memset(v,0,sizeof(v));
    }
    void unit()
    {
        for(int i=0; i<dim; i++) v[i][i]=1;
    }
    matrix operator *(matrix a)
    {
        matrix rez;
        for (int i=0; i<dim; ++i)
            for (int j=0; j<dim; ++j)
                for (int y=0; y<dim; ++y)
                    rez.v[i][j]=(rez.v[i][j]+1LL*v[i][y]*a.v[y][j])%mod;
        return rez;
    }
};

matrix pow(matrix a,int power)
{
    matrix p;
    p.unit();
    for(int i=1; i<=power; i<<=1)
    {
        if(power&i) p=p*a;
        a=a*a;
    }
    return p;
}

int64_t inmultire(int x,int y,int z,int a,int b,int c,int target)
{
    int result=0;
    matrix magic;
    magic.v[0][2]=c;
    magic.v[1][2]=b;
    magic.v[2][2]=a;
    magic.v[1][0]=magic.v[2][1]=1;
    magic=pow(magic,target);
    result=x*magic.v[0][0]+y*magic.v[1][0]+z*magic.v[2][0];
    return result;
}

int main()
{
    int q,x,y,z,a,b,c;
    int32_t n;
    f>>q;
    for (int i=0; i<q; ++i)
    {
        f>>x>>y>>z>>a>>b>>c>>n;
        t<<inmultire(x,y,z,a,b,c,n)<<'\n';
    }
    return 0;
}