using namespace std;
#include<iostream>
#include<fstream>
#include<vector>

#define MOD 666013

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

int t, n;
long long s[4][4];
long long a[4][4];
long long b[4][4];

void I3(long long b[4][4]);
void exp_rapida(long long b[4][4], long long a[4][4], int n);
void inmultire_sir(long long b[4][4], long long s[4][2]);
void inmultire(long long b[4][4], long long a[4][4]);
void afisare(long long a[4][4]);

int main() {

    fin >> t;
    while (t--) {
        a[1][1] = 0, a[1][2] = 1, a[1][3] = 0;
        a[2][1] = 0, a[2][2] = 0, a[2][3] = 1;
        fin >> s[1][1] >> s[2][1] >> s[3][1];
        fin >> a[3][3] >> a[3][2] >> a[3][1];
        fin >> n;
        
        I3(b);
        exp_rapida(b, a, n);
       // afisare(s);
        //afisare(b);
        inmultire(b, s);
        // afisare(b);
        fout << b[1][1] << "\n";
    }
        
    return 0;
}

void afisare(long long a[4][4]) {
    for (int i = 1; i<=3; i++) {
        for (int j = 1; j<=3; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}

long long c[4][4];

void inmultire(long long b[4][4], long long a[4][4]) {
    
    for (int i = 1; i<=3; i++) {
        for (int j = 1; j<=3; j++) {
            c[i][j] = 0;
            for (int k = 1; k<=3; k++) {
                c[i][j] = (c[i][j] + (b[i][k] * a[k][j]) % MOD) % MOD;
            }
        }
    }
    
    for (int i = 1; i<=3; i++) {
        for (int j = 1; j<=3; j++) {
            b[i][j] = c[i][j];
        }
    }
}

void exp_rapida(long long b[4][4], long long a[4][4], int n) {
    
    while (n) {
        if (n % 2 == 1) {
            inmultire(b, a);
        }
        inmultire(a, a);
        n /= 2;
    }
    
}

void I3(long long b[4][4]) {
    for (int i = 1; i<=3; i++) {
        for (int j = 1; j<=3; j++) {
            if (i == j) {
                b[i][j] = 1;
            } else {
                b[i][j] = 0;
            }
        }
    }
}