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

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

const int mod = 666013;

struct matrix {
    int m[3][3];
}m;

int a, b ,c, n, t;
int v[4];

///40p O(n)
/*void solve() {
    for(int i = 3; i <= n; i++) {
        v[3] = (a*v[2] + b*v[1] + c*v[0])%mod;
        for(int k = 0; k < 3; k++)
            v[k] = v[k+1];
    }
    fout << v[3] << '\n';
}*/

matrix inmultire(matrix a, matrix b) {
    matrix res;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++) {
            res.m[i][j] = 0;
            for(int k = 0; k < 3; k++)
                res.m[i][j] = (res.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
        }
    return res;
}

matrix putereMat(int p) {
    if(p == 1)
        return m;
    if(p%2)
        return inmultire(putereMat(p-1), m);
    return inmultire(putereMat(p/2), putereMat(p/2));

}

void solve() {
    m.m[0][0] = 0;
    m.m[0][1] = 1;
    m.m[0][2] = 0;
    m.m[1][0] = 0;
    m.m[1][1] = 0;
    m.m[1][2] = 1;
    m.m[2][0] = c;
    m.m[2][1] = b;
    m.m[2][2] = a;

    matrix mat = putereMat(n-2);
    fout << (mat.m[2][0]*v[0] + mat.m[2][1]*v[1] + mat.m[2][2]*v[2])%mod << '\n';
}

int main() {
    fin >> t;
    while(t--) {
        fin >> v[0] >> v[1] >> v[2] >> a >> b >> c >> n;
        solve();
    }
}