#include <bits/stdc++.h>
#ifdef JOON
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;

template<class ModWrapper>
class modular {
private:
    using T = typename decay<decltype(ModWrapper::value)>::type;
    T value;

public:
    using value_type = T;

    constexpr modular() : value() {}

    constexpr static T mod() {
        return ModWrapper::value;
    }

    template<class V>
    static T norm(const V &x) {
        T val;
        if (x >= static_cast<V>(0)) {
            val = static_cast<T>(x < mod() ? x : x % mod());
        } else {
            val = static_cast<T>(-x <= mod() ? x : x % mod());
            if (val < static_cast<T>(0)) {
                val += mod();
            }
        }
        return val;
    }

    template<class V>
    modular(const V &x) : value(norm(x)) {}

    template<class V>
    explicit operator V() const {
        return static_cast<V>(value);
    }

    modular &operator+=(const modular &other) {
        if (value < mod() - other.value) {
            value += other.value;
        } else {
            value -= mod() - other.value;
        }
        return *this;
    }

    modular &operator-=(const modular &other) {
        if (value >= other.value) {
            value -= other.value;
        } else {
            value += mod() - other.value;
        }
        return *this;
    }

    template<class V = T>
    typename enable_if<(sizeof(V) <= 4), modular>::type &operator*=(const modular &other) {
        value = norm(static_cast<int64_t>(value) * static_cast<int64_t>(other.value));
        return *this;
    }

    template<class V = T>
    typename enable_if<(sizeof(V) > 4 && sizeof(V) <= 8), modular>::type &operator*=(const modular &other) {
        using i128 = __int128;
        value = norm(static_cast<i128>(value) * static_cast<i128>(other.value));
        return *this;
    }

    modular inverse() const {
        T u = static_cast<T>(0), v = static_cast<T>(1);
        T a = value, m = mod();
        while (a != static_cast<T>(0)) {
            T t = m / a;
            m -= t * a;
            swap(a, m);
            u -= t * v;
            swap(u, v);
        }
        assert(m == 1);
        return modular(u);
    }

    modular &operator/=(const modular &other) {
        return *this *= other.inverse();
    }

    modular operator+(const modular &other) const {
        return modular(*this) += other;
    }

    modular operator-(const modular &other) const {
        return modular(*this) -= other;
    }

    modular operator*(const modular &other) const {
        return modular(*this) *= other;
    }

    modular operator/(const modular &other) const {
        return modular(*this) /= other;
    }

    bool operator==(const modular &other) const {
        return value == other.value;
    }

    bool operator!=(const modular &other) const {
        return !(*this == other);
    }

    template<class V>
    modular pow(const V &b) {
        bool inv = b < static_cast<V>(0);
        modular res(static_cast<T>(1));
        modular x(inv ? inverse() : *this);
        V p = inv ? -b : b;
        while (p > static_cast<V>(0)) {
            if (p & 1) {
                res *= x;
            }
            x *= x;
            p >>= 1;
        }
        return res;
    }

    template<class V> modular &operator+=(const V &other) { return *this += modular(other); }
    template<class V> modular &operator-=(const V &other) { return *this -= modular(other); }
    template<class V> modular &operator*=(const V &other) { return *this *= modular(other); }
    template<class V> modular &operator/=(const V &other) { return *this /= modular(other); }
    template<class V> modular operator+(const V &other) const { return *this + modular(other); }
    template<class V> modular operator-(const V &other) const { return *this - modular(other); }
    template<class V> modular operator*(const V &other) const { return *this * modular(other); }
    template<class V> modular operator/(const V &other) const { return *this / modular(other); }
    modular &operator++() { return *this += 1; }
    modular &operator--() { return *this -= 1; }
    modular operator++(int) { modular res(*this); *this += 1; return res; }
    modular operator--(int) { modular res(*this); *this -= 1; return res; }
    modular operator-() const { return modular(-value); }
    T operator()() const { return value; }

    template<class W>
    friend istream &operator>>(istream &in, modular<W> &n);
};

template<class V, class W> modular<W> operator+(const V &lhs, const modular<W> &rhs) { return modular<W>(lhs) + rhs; }
template<class V, class W> modular<W> operator-(const V &lhs, const modular<W> &rhs) { return modular<W>(lhs) - rhs; }
template<class V, class W> modular<W> operator*(const V &lhs, const modular<W> &rhs) { return modular<W>(lhs) * rhs; }
template<class V, class W> modular<W> operator/(const V &lhs, const modular<W> &rhs) { return modular<W>(lhs) / rhs; }
template<class V, class W> bool operator==(const V &lhs, const modular<W> &rhs) { return modular<W>(lhs) == rhs; }
template<class V, class W> bool operator!=(const V &lhs, const modular<W> &rhs) { return modular<W>(lhs) != rhs; }

template<class W>
ostream &operator<<(ostream &out, const modular<W> &n) {
    return out << n();
}

template<class W>
istream &operator>>(istream &in, modular<W> &n) {
    typename common_type<typename modular<W>::value_type, int64_t>::type x;
    in >> x;
    n.value = modular<W>::norm(x);
    return in;
}

struct varmod {
    static int value;
};
int varmod::value;
int &md = varmod::value;
using Mint = modular<varmod>;

template<class T>
class matrix {
public:
    int n, m;
    vector<vector<T>> entry;

    matrix(int n_, int m_) : n(n_), m(m_), entry(n_, vector<T>(m_)) {}
    matrix(int n_) : matrix(n_, n_) {}

    T& operator[](const pair<int, int>& p) {
        return entry[p.first][p.second];
    }

    const T& operator[](const pair<int, int>& p) const {
        return entry[p.first][p.second];
    }
};

template<class T>
matrix<T> matmul(const matrix<T>& A, const matrix<T>& B) {
    assert(A.m == B.n);
    matrix<T> C(A.n, B.m);
    for (int i = 0; i < C.n; i++) {
        for (int k = 0; k < A.m; k++) {
            for (int j = 0; j < C.m; j++) {
                C[{i, j}] += A[{i, k}] * B[{k, j}];
            }
        }
    }
    return C;
}

using poly = vector<Mint>;

void polyadd(poly &p, const poly &q, size_t sh = 0, Mint mt = 1) {
    p.resize(max(p.size(), q.size() + sh));
    for (int i = 0; i < (int)q.size(); i++) {
        p[i + sh] += q[i] * mt;
    }
    while (!p.empty() && p.back() == 0) {
        p.pop_back();
    }
}

poly polymul(const poly &p, const poly &q) {
    if (p.empty() || q.empty()) {
        return {};
    }
    int pd = (int)p.size() - 1, qd = (int)q.size() - 1;
    poly res(pd + qd + 1);
    for (int i = 0; i <= pd; i++) {
        for (int j = 0; j <= qd; j++) {
            res[i + j] += p[i] * q[j];
        }
    }
    return res;
}

void polymod(poly &p, const poly &m) {
    while (p.size() >= m.size()) {
        polyadd(p, m, p.size() - m.size(), -p.back() / m.back());
    }
}

poly &operator+=(poly &p, const poly &q) {
    polyadd(p, q);
    return p;
}

poly f_A;

poly operator*(const poly &p, const poly &q) {
    auto res = polymul(p, q);
    polymod(res, f_A);
    return res;
}

template<class T>
matrix<T> matpow(matrix<T> A, long long r) {
    assert(A.n == A.m);
    matrix<T> R(A.n);
    for (int i = 0; i < A.n; i++) {
        R[{i, i}] = {1};
    }
    while (r) {
        if (r & 1) {
            R = matmul(R, A);
        }
        A = matmul(A, A);
        r >>= 1;
    }
    return R;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tt;
    cin >> tt;
    array<array<vector<int>, 18>, 2> D;
    D[0][0] = D[1][0] = {1};
    D[0][1] = {-1, 1};
    D[1][1] = {-2, 1};
    for (int i = 2; i <= 17; i++) {
        for (auto &dp : D) {
            dp[i].resize(i + 1);
            dp[i][i] = 1;
            for (int j = 0; j < i; j++) {
                dp[i][j] = -2 * dp[i - 1][j];
                if (j) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
                if (j < i - 1) {
                    dp[i][j] -= dp[i - 2][j];
                }
            }
        }
    }
    matrix<poly> M(2);
    M[{0, 0}] = {2, 1};
    M[{0, 1}] = {-1};
    M[{1, 0}] = {1};
    while (tt--) {
        long long n;
        int m;
        cin >> m >> n >> md;
        if (n & m & 1) {
            cout << "0\n";
            continue;
        }
        if (m == 1) {
            cout << "1\n";
            continue;
        } else if (m == 2) {
            matrix<Mint> C(2);
            C[{0, 0}] = C[{0, 1}] = C[{1, 0}] = 1;
            cout << matpow(C, n)[{0, 0}] << "\n";
            continue;
        } else if (m == 3) {
            matrix<Mint> C(2);
            C[{0, 0}] = 4;
            C[{0, 1}] = -1;
            C[{1, 0}] = 1;
            auto R = matpow(C, n >> 1);
            cout << R[{0, 0}] + R[{0, 1}] << "\n";
            continue;
        } else if (m == 4) {
            matrix<Mint> C(4);
            C[{0, 0}] = C[{0, 2}] = C[{1, 0}] = C[{2, 1}] = C[{3, 2}] = 1;
            C[{0, 1}] = 5;
            C[{0, 3}] = -1;
            auto R = matpow(C, n);
            cout << 5 * R[{2, 0}] + R[{2, 1}] + R[{2, 2}] << "\n";
            continue;
        } else if (m == 5) {
            matrix<Mint> C(4);
            C[{1, 0}] = C[{2, 1}] = C[{3, 2}] = 1;
            C[{0, 0}] = C[{0, 2}] = 15;
            C[{0, 1}] = -32;
            C[{0, 3}] = -1;
            auto R = matpow(C, n >> 1);
            cout << 1183 * R[{3, 0}] + 95 * R[{3, 1}] + 8 * R[{3, 2}] + R[{3, 3}] << "\n";
            continue;
        }
        f_A.resize((m >> 1) + 1);
        for (int i = 0; i <= (m >> 1); i++) {
            f_A[i] = D[m & 1][m >> 1][i];
        }
        auto R = matpow(M, n >> 1);
        auto f_B = R[{0, 0}];
        if (~n & 1) {
            polyadd(f_B, R[{0, 1}]);
        }
        Mint res = 1;
        while ((int)f_B.size() > 1) {
            swap(f_A, f_B);
            if (~f_A.size() & ~f_B.size() & 1) {
                res = -res;
            }
            auto e = f_B.size();
            polymod(f_B, f_A);
            res *= f_A.back().pow(e - f_B.size());
        }
        if (!f_B.empty()) {
            res *= f_B[0].pow(f_A.size() - 1);
        } else {
            res = 0;
        }
        cout << res << "\n";
    }
    return 0;
}