#include <cstdio>
#include <fstream>
#define mod 666013
using namespace std;
ifstream f("iepuri.in");
ofstream g("iepuri.out");
long long sol[5][5],m1[5][5],m2[5][5];



void prod1()
{
    int i,j,k;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            m2[i][j]=0;

    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            for (k=1;k<=3;k++)
                m2[i][j]=(1LL*m2[i][j]+sol[i][k]*m1[k][j])%mod;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            sol[i][j]=m2[i][j]%mod;
}
void prod2()
{
    int i,j,k;
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            m2[i][j]=0;

    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            for (k=1;k<=3;k++) m2[i][j]=(1LL*m2[i][j]+m1[i][k]*m1[k][j])%mod;

    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
            m1[i][j]=m2[i][j]%mod;


}
int solveone()
{
    for (int i=1;i<=3;i++)
        for (int j=1;j<=3;j++) {
            m1[i][j]=0;
            sol[i][j]=0;
        }

    int x,y,z,a,b,c,n;
    f>>x>>y>>z>>a>>b>>c>>n;
    if (n==3) return z;
    n-=2;
    sol[1][1]=x;
    sol[1][2]=y;
    sol[1][3]=z;
    m1[2][1]=1;
    m1[3][2]=1;
    m1[1][3]=c;
    m1[2][3]=b;
    m1[3][3]=a;

    while (n) {
        if (n&1) {
            prod1();
        }
        prod2();
        n>>=1;
    }
    return sol[1][3];

}

int main()
{
    int t;
    f>>t;
    while (t) {
        --t;
        g<<solveone()<<'\n';
    }
    return 0;
}