solve

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll nmax = 1e9+7;
const ll nmax2 = 998244353;

void solve(){

    ll a, b, c, d, e;
    std::cin >> a >> b >> c >> d >> e;

    ll n;
    std::cin >> n;

    if (n == 1){
        std::cout << 0 << '\n';
        return;
    } else if (n == 2){
        std::cout << 1 << '\n';
        return;
    } else if (n == 3){
        std::cout << 2 << '\n';
        return;
    } else if (n == 4){
        std::cout << 3 << '\n';
        return;
    }

    std::vector<std::vector<ll>> adj(5, std::vector<ll>(5));
    adj[0][0] = a;
    adj[0][1] = b;
    adj[0][2] = c;
    adj[0][3] = d;
    adj[0][4] = e;

    adj[1][0] = 1;
    adj[1][1] = 0;
    adj[1][2] = 0;
    adj[1][3] = 0;
    adj[1][4] = 0;

    adj[2][0] = 0;
    adj[2][1] = 1;
    adj[2][2] = 0;
    adj[2][3] = 0;
    adj[2][4] = 0;

    adj[3][0] = 0;
    adj[3][1] = 0;
    adj[3][2] = 1;
    adj[3][3] = 0;
    adj[3][4] = 0;

    adj[4][0] = 0;
    adj[4][1] = 0;
    adj[4][2] = 0;
    adj[4][3] = 0;
    adj[4][4] = 1;

    auto matrix_self = [&] (std::vector<std::vector<ll>> &vect, ll k) -> void {
        std::vector<std::vector<ll>> res(k, std::vector<ll>(k, 0));
        for (ll i = 0; i < k; i++){
            for (ll j = 0; j < k; j++){
                ll ans = 0;
                for (ll l = 0; l < k; l++){
                    ans += vect[i][l] * vect[l][j];
                    ans %= nmax;
                }
                res[i][j] = ans;
            }
        }
        for (ll i = 0; i < k; i++){
            for (ll j = 0; j < k; j++) vect[i][j] = res[i][j];
        }
    };

    auto matrix_mul = [&] (std::vector<std::vector<ll>> vect1, std::vector<std::vector<ll>> vect2) -> std::vector<std::vector<ll>> {
        std::vector<std::vector<ll>> res(5, std::vector<ll>(1, 0));
        res[0][0] = vect1[0][0] * vect2[0][0] + vect1[0][1] * vect2[1][0] + vect1[0][2] * vect2[2][0] + vect1[0][3] * vect2[3][0] + vect1[0][4] * vect2[4][0];
        res[0][0] %= nmax;
        res[1][0] = vect1[1][0] * vect2[0][0] + vect1[1][1] * vect2[1][0] + vect1[1][2] * vect2[2][0] + vect1[1][3] * vect2[3][0] + vect1[1][4] * vect2[4][0];
        res[1][0] %= nmax;
        res[2][0] = vect1[2][0] * vect2[0][0] + vect1[2][1] * vect2[1][0] + vect1[2][2] * vect2[2][0] + vect1[2][3] * vect2[3][0] + vect1[2][4] * vect2[4][0];
        res[2][0] %= nmax;
        res[3][0] = vect1[3][0] * vect2[0][0] + vect1[3][1] * vect2[1][0] + vect1[3][2] * vect2[2][0] + vect1[3][3] * vect2[3][0] + vect1[3][4] * vect2[4][0];
        res[3][0] %= nmax;
        res[4][0] = vect1[4][0] * vect2[0][0] + vect1[4][1] * vect2[1][0] + vect1[4][2] * vect2[2][0] + vect1[4][3] * vect2[3][0] + vect1[4][4] * vect2[4][0];
        res[4][0] %= nmax;
        return res;
    };

    auto matrix_exp = [&] (ll m, std::vector<std::vector<ll>> A) -> std::vector<std::vector<ll>> {
        std::vector<std::vector<ll>> fin(5, std::vector<ll>(1, 0));
        fin[0][0] = 3;
        fin[1][0] = 2;
        fin[2][0] = 1;
        fin[3][0] = 0;
        fin[4][0] = 1;
        while (m > 0){
            if (m & 1) fin = matrix_mul(A, fin);
            matrix_self(A, 5);
            m >>= 1;
        }
        return fin;
    };

    auto final_answer = matrix_exp(n - 4, adj);
    std::cout << final_answer[0][0] << '\n';
}

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int t;
    std::cin >> t;
    // t = 1;
    while(t--){
        solve();
    }
    return 0;
}