#include <iostream>
#include <cstdio>
#define mod 666013

using namespace std;

class matrice
{
private:
    int n, a[5][5];
public:
    matrice()
    {
        for(int i=0;i<5;i++)
            for(int j=0;j<5;j++)
                a[i][j]=0;
        n=0;
    }
    matrice(int nn, int x)
    {
        n=nn;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                a[i][j]=x;
    }
    matrice(int nn)
    {
        n=nn;
        a[0][0]=0;
        a[1][0]=1;
        a[2][0]=0;
        a[0][1]=0;
        a[1][1]=0;
        a[2][1]=1;
        a[0][2]=1;
        a[1][2]=1;
        a[2][2]=1;
    }
    int* operator[](const int i)
    {
        return this->a[i];
    }
    void setElem(int i, int j, int x)
    {
        a[i][j]=x;
    }
    int getElem(int i, int j)
    {
        return a[i][j];
    }
    void setN(int x)
    {
        n=x;
    }
    int getN()
    {
        return n;
    }
    matrice &operator =(const matrice &b)
    {
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                this->a[i][j]=b.a[i][j];
        return *this;
    }
    matrice operator +(const matrice &b)
    {
        matrice c=matrice();
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                c[i][j]=this->a[i][j]+b.a[i][j];
        c.n=nn;
        return c;
    }
    matrice operator -(const matrice &b)
    {
        matrice c=matrice();
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                c[i][j]=this->a[i][j]-b.a[i][j];
        c.n=nn;
        return c;
    }
    matrice operator * (const matrice &b)
    {
        matrice c=matrice();
        int nn=this->n;
        for(int i=0;i<nn;i++)
            for(int j=0;j<nn;j++)
                for(int k=0;k<nn;k++)
                    c[i][j]=((1LL*c[i][j])%mod+1LL*(1LL*(1LL*this->a[i][k]%mod)*(1LL*b.a[k][j]%mod)%mod))%mod;
        c.n=nn;
        return c;
    }
    void putere(int p, matrice &c, const matrice b)
    {
        if(p==1)
            return;
        if(p%2==0)
        {
            (*this).putere(p/2, c, b);
            c=c*c;
            *this=c;
//            cout<<p<<"\n";
//            c.afisare();
        }
        else
        {
            (*this).putere(p-1, c, b);
            c=c*b;
            *this=c;
//            cout<<p<<"\n";
//            c.afisare();
        }
    }
    void afisare()
    {
        int nn=this->n;
        for(int i=0;i<nn;i++)
        {
            for(int j=0;j<nn;j++)
                cout<<this->a[i][j]<<" ";
            cout<<"\n";
        }
    }
};

int x, y, z, a, b, c, n, t;

int main()
{
    freopen("iepuri.in", "r", stdin);
    freopen("iepuri.out", "w", stdout);

    scanf("%d\n", &t);
    for(int test=0;test<t;test++)
    {
        scanf("%d %d %d %d %d %d %d\n", &x, &y, &z, &a, &b, &c, &n);
        matrice mat=matrice(3);
        mat.setElem(0, 2, c);
        mat.setElem(1, 2, b);
        mat.setElem(2, 2, a);
        mat.putere(n-2, mat, mat);
        a=mat.getElem(0, 2);
        b=mat.getElem(1, 2);
        c=mat.getElem(2, 2);
        printf("%d\n", (((a*x*1LL)%mod+(b*y*1LL)%mod)%mod+(c*z*1LL)%mod)%mod);
    }
}