#include <iostream>
#include <fstream>

#define MOD 666013
 
using namespace std;

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

void afisare(int mat[4][4])
{
    for (int i=1;i<=3;i++)
    {
        for (int j=1;j<=3;j++)
            cout<<mat[i][j]<<' ';
        cout<<'\n';
    }
    cout<<'\n';
}

void init(int mat[4][4])
{
    mat[1][1]=0;
    mat[1][2]=1;
    mat[1][3]=0;
    mat[2][1]=0;
    mat[2][2]=0;
    mat[2][3]=1;
    mat[3][1]=c;
    mat[3][2]=b;
    mat[3][3]=a;
}

void multire(int a1[4][4],int a2[4][4])
{
    int c[4][4];
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            c[i][j]=0;
    for (int i=1; i<=3; i++)
        for (int j=1; j<=3; j++)
            for (int k=1; k<=3; k++)
                c[i][j]=(c[i][j]+(1LL*a1[i][k]*a2[k][j])%MOD)%MOD;
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            a1[i][j]=c[i][j];
}

void putere(int a[4][4],int put)
{
    int rez[4][4];
    init(rez);
    for (int i=2;i<=put;i++)
        multire(rez, a);
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++)
            a[i][j]=rez[i][j];
    return;

    /*int b[4][4];
    
    init(b);
    
    while(put)
    {
        if(put%2)
        {
            multire(b, a);
            put--;
        }
        else
        {
            multire(a,a);
            put/=2;
        }
    }
    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            a[i][j] = b[i][j];*/
}

int main()
{
    ifstream fin ("iepuri.in");
    ofstream fout ("iepuri.out");
    int m;
    fin>>m;
    for (int q=0;q<m;q++)
    {
        int n,m1[4][4],m2[4][4];
        fin>>x>>y>>z>>a>>b>>c>>n;
        init(m1);
        putere(m1, n-2);
        
        m2[1][1]=x;
        m2[2][1]=y;
        m2[3][1]=z;
        m2[1][2]=m2[1][3]=m2[2][2]=m2[2][3]=m2[3][2]=m2[3][3]=0;
        
        multire(m1, m2);
        fout<<m1[3][1]<<'\n';
    }
    return 0;
}