#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin("iepuri.in");
ofstream fout("iepuri.out");

const int MOD = 666013;

int a[3][3], iep[3][3];

void restinit() {
    for (int i = 1; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            iep[i][j] = a[j][i] = 0;
        }
    }
    a[0][1] = 1;
    a[1][2] = 1;
}

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

void fast_exp(int n) {
    while (n) {
        if ((n&1)) {
            multiplication(iep, a);
        }
        n = (n>>1);
        multiplication(a, a);
    }
}

int main() {
    int t, n;
    fin>>t;
    while (t--) {
        fin>>iep[0][2]>>iep[0][1]>>iep[0][0];
        fin>>a[0][0]>>a[1][0]>>a[2][0];
        restinit();
        fin>>n;
        fast_exp(n);

        fout<<iep[0][2]<<endl;
    }

    fin.close();
    fout.close();
    return 0;
}