#include <fstream>
#define mod 666013
using namespace std;
int prod1(int a[4], int b[4][4])
{
    int c=0;
    int k;
    for (k=1;k<=3;k++)
        c+=(a[k]*b[k][2]);
    return c%mod;
}
void prod2(int a[4][4],int b[4][4])
{
    int i,j,k;
    int c[4][4];
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++)
        {
            c[i][j]=0;
            for (k=1;k<=3;k++)
                c[i][j]+=(a[i][k]*b[k][j]);
        }
    for (i=1;i<=3;i++)
        for (j=1;j<=3;j++) a[i][j]=c[i][j]%mod;
}
void expon(int a[4][4],long long n)
{
    int i,j;
    if(n>1)
    {
        int b[4][4];
        int c[4][4];
        for (i=1
             ;i<=3;i++)
            for (j=1;j<=3;j++)
                b[i][j]=c[i][j]=a[i][j];
        if (!(n%2))
        {
            expon(b,n/2);
            expon(c,n/2);
            prod2(b,c);
            for (i=1;i<=3;i++)
                for (j=1;j<=3;j++)
                    a[i][j]=b[i][j];
        }
        else
        {
            expon(b,n/2);
            expon(c,n/2);
            prod2(b,c);
            prod2(a,b);
        }
    }
}
int main()
{
    ifstream f("iepuri.in");
    ofstream g("iepuri.out");
    long long n;
    int m1[4];int aa[4][4];
    int t,i,x,y,z,a,b,c;
    f>>t;
    for (i=1;i<=t;i++)
    {
        f>>x>>y>>z>>a>>b>>c>>n;
        m1[1]=x;m1[2]=y;m1[3]=z;
        aa[1][1]=aa[1][2]=aa[2][2]=aa[3][1]=0;
        aa[2][1]=aa[3][2]=1;
        aa[1][3]=c;aa[2][3]=b;aa[3][3]=a;
        expon(aa,n-1);
        g<<prod1(m1,aa)<<'\n';
    }
    f.close();
    g.close();
    return 0;
}