#include <iostream>
#include <fstream>
#define MOD 666013
using namespace std;

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

long long x,y,zz,a,b,c,n,t;
long long g[3][3],z[3][3];

void init()
{
    g[0][0] = x;
    g[0][1] = y;
    g[0][2] = zz;
    g[1][0] = 0;
    g[1][1] = 0;
    g[1][2] = 0;
    g[2][0] = 0;
    g[2][1] = 0;
    g[2][2] = 0;

    z[0][0] = 0;
    z[0][1] = 0;
    z[0][2] = c;

    z[1][0] = 1;
    z[1][1] = 0;
    z[1][2] = b;

    z[2][0] = 0;
    z[2][1] = 1;
    z[2][2] = a;

}

void inmultire(long long a[3][3],long long b[3][3])
{
    long long c[3][3];
    for(long long i=0;i<3;i++)
        for(long long j=0;j<3;j++)
            c[i][j] = 0;

    for(long long i=0;i<3;i++)
    {
        for(long long j=0;j<3;j++)
        {
            for(long long k=0;k<3;k++)
            {
                c[i][j] = c[i][j] + a[i][k]*b[k][j];
            }
            c[i][j] = c[i][j]%MOD;
        }
    }

    for(long long i=0;i<3;i++)
        for(long long j=0;j<3;j++)
            a[i][j] = c[i][j];
}

void af()
{
     for(long long i=0;i<3;i++)
        {
            for(long long j=0;j<3;j++)
                cout << g[i][j] << " ";
            cout << endl;
        }
        cout << endl;
}

long long rez()
{
    init();

    n = n-2;
    while(n>1)
    {
        if(n%2==1)
        {
            inmultire(g,z);
            n--;
        }
        n = n/2;
        inmultire(z,z);

    }
    inmultire(g,z);
    return (g[0][2]%MOD);
}

int main()
{
    in >> t;
    for(long long i=0;i<t;i++)
    {
        in >> x >> y >> zz >> a >> b >> c >> n;
        out << rez() << "\n";
        //af();
  }
    return 0;
}