#include <fstream>

using namespace std;

ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

int m[4][4],f[4];
int rez[4][4];

void inm(int a[4][4], int b[4][4])
{
    int c[4][4]={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]+=1LL*a[i][k]*b[k][j]%666013;
                c[i][j]%=666013;
            }
        }
    }
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            a[i][j]=c[i][j];
        }
    }
}

int rezultat(int n)
{
    int fr[4]={0};
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
        {
            rez[i][j]=0;
            if(i==j)
                rez[i][j]=1;
        }
    n-=2;
    while(n>0)
    {
        if(n%2==1)
        {
            inm(rez,m);
            n--;
        }
        else
        {
            inm(m,m);
            n/=2;
        }
    }
    for(int i=1;i<=3;i++)
    {
        for(int k=1;k<=3;k++)
        {
            fr[i]+=(1LL*rez[i][k]*f[k])%666013;
            fr[i]%=666013;
            m[i][k]=0;
        }
    }
    return fr[3];
}

int main()
{
    short t;
    fin>>t;
    for(short q=1;q<=t;q++)
    {
        for(int i=1;i<=2;i++)
            m[i][i+1]=1;
        int n;
        fin>>f[1]>>f[2]>>f[3]>>m[3][3]>>m[3][2]>>m[3][1]>>n;
        fout<<rezultat(n)<<'\n';
    }
    return 0;
}