#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
#include <map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
//#include <iostream>
using namespace std;
ifstream cin("iepuri.in");
ofstream cout("iepuri.out");
int MOD = 666013;
struct matrice{
    unsigned long long a, b, c, d, e, f, g, h, i;
};
matrice x, y;
matrice inmultire(matrice x, matrice y)
{
    matrice z;
    z.a = (x.a * y.a + x.b * y.d + x.c * y.g) % MOD;
    z.b = (x.a * y.b + x.b * y.e + x.c * y.h) % MOD;
    z.c = (x.a * y.c + x.b * y.f + x.c * y.i) % MOD;
    z.d = (x.d * y.a + x.e * y.d + x.f * y.g) % MOD;
    z.e = (x.d * y.b + x.e * y.e + x.f * y.h) % MOD;
    z.f = (x.d * y.c + x.e * y.f + x.f * y.i) % MOD;
    z.g = (x.g * y.a + x.h * y.d + x.i * y.g) % MOD;
    z.h = (x.g * y.b + x.h * y.e + x.i * y.h) % MOD;
    z.i = (x.g * y.c + x.h * y.f + x.i * y.i) % MOD;
    return z;
}
matrice putere(matrice x, int e, matrice neutru)
{
    if(e == 0)
        return neutru;
    if(e % 2 == 0)
    {
        matrice inlocuitor = putere(x, e / 2, neutru);
        return inmultire(inlocuitor, inlocuitor);
    }
    else
        return inmultire(x, putere(x, e - 1, neutru));
}
int main(){
    int n;
    cin >> n;
    matrice neutru;
    neutru.a = 1; neutru.b = 0; neutru.c = 0;
    neutru.d = 0; neutru.e = 1; neutru.f = 0;
    neutru.g = 0; neutru.h = 0; neutru.i = 1;
    for(int i = 0; i < n; i++){
        int aa, bb, cc, dd, ee, ff, nr;
        cin >> aa >> bb >> cc >> dd >> ee >> ff >> nr;
        x.a = 0; x.b = 0; x.c = ff;
        x.d = 1; x.e = 0; x.f = ee;
        x.g = 0; x.h = 1; x.i = dd;
        matrice rezult = putere(x, nr - 2, neutru);
        x = rezult;
        cout << ((aa * rezult.c) % MOD + (bb * rezult.f) % MOD + (cc * rezult.i) % MOD) % MOD << "\n";
    }
    return 0;
}