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

constexpr int mod = 666013;

/* Calculeaza a * b mod p; p reprezinta polynomiul p[0] + p[1] X + ... + p[N-1]
 * X^(N-1) - X^N */
template <int N>
static constexpr array<int, N> poly_mul(array<int, N> a, array<int, N> b, array<int, N> p){
    array<long long, 2 * N - 1> t = {};
    for(int i = 0; i < N; ++i)
        for(int j = 0; j < N; ++j)
            t[i + j] = (t[i + j] + (long long)a[i] * b[j])%mod;
    for(int i = 2 * N - 2; i >= N; --i)
        for(int j = 0; j < N; ++j)
            t[i - N + j] = (t[i - N + j] + t[i] * p[j]) % mod;
    array<int, N> r;
    for(int i = 0; i < N; ++i) r[i] = t[i];
    return r;
}

template <int N>
static constexpr array<int, N> lgput(array<int, N> a, int x, array<int, N> p, array<int, N> r = {1, 0}){
    return x == 0 ? r : lgput<N>(poly_mul<N>(a, a, p), x / 2, p, x % 2 ? poly_mul<N>(a, r, p) : r);
}

template <int N>
static constexpr int mod_inner_product(array<int, N> a, array<int, N> b){
    int ret = 0;
    for(int i = 0; i < N; ++i) ret = (ret + (long long) a[i] * b[i]) %mod;
    return ret;
}

ifstream f("iepuri.in");
ofstream g("iepuri.out");

int main(){
    int t;
    f >> t;
    while(t--){
        array<int, 3> init, poly;
        for(auto& x : init) f >> x;
        for(int i = 2; i >= 0; --i) f >> poly[i];
        int n;
        f >> n;
        auto p = lgput<3>(array<int, 3>{0, 1, 0}, n, poly);

        g << mod_inner_product<3>(lgput<3>(array<int, 3>{0, 1, 0}, n, poly), init) << '\n';
    }
}