#include <iostream>
#include <fstream>
#define ll long long
#define mod 666013
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");
int x0,x1,x2,x,y,z,n;
ll m[5][5];
void citire()
{
    fin>>x0>>x1>>x2>>x>>y>>z>>n;
}
void init(ll a[5][5])
{
    a[1][1]=x;
    a[1][2]=y;
    a[1][3]=z;
    a[2][1]=a[3][2]=1;
    a[2][2]=a[2][3]=a[3][1]=a[3][3]=0;
}
void inmultire(ll a[5][5], ll b[5][5])
{
    ll rez[5][5]={0};
   for(int i = 1; i <= 3; ++i)
        for(int k = 1; k <= 3; ++k)
            for(int j = 1; j <= 3; ++j)
            rez[i][k] = (rez[i][k] + a[i][j] * b[j][k] ) % mod;

    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            a[i][j] = rez[i][j];
}

void putere(ll a[5][5],ll p)
{
    ll b[5][5];
    init(b);
    while(p)
    {
        if(p%2)
    {
       inmultire(b,a);
        p--;

    }
    else
    {   inmultire(a,a);
        p/=2;
    }
    }
    for(int i = 1; i <= 3; ++i)
        for(int j = 1; j <= 3; ++j)
            a[i][j] = b[i][j];
}
int main()
{   int q;
    fin>>q;
    for(int i=1; i<=q; i++)
    {
        citire();
    init(m);
    putere(m,n-1);
    ll rasp=0;
    rasp=(rasp+(m[3][1]*x2)%mod)%mod;
    rasp=(rasp+(m[3][2]*x1)%mod)%mod;
    rasp=(rasp+(m[3][3]*x0)%mod)%mod;
    fout<<rasp<<"\n";
    }

    return 0;
}