#include <bits/stdc++.h>

using namespace std;

const int N = 16;

int P, G, iG, fac[(1 << N) + 5], iFac[(1 << N) + 5];
int f[N + 1][N + 1][1 << N], g[N + 1][N + 1][1 << N];

int ksm(int x, int y = P - 2) {
    int res = 1;
    while (y) {
        if (y & 1) res = 1ll * res * x % P;
        x = 1ll * x * x % P;
        y >>= 1;
    }
    return res;
}

int C(int x, int y) {
    return 1ll * fac[x] * iFac[y] % P * iFac[x - y] % P;
}

vector<int> arr;

void divide() {
    int p = P - 1;
    for (int i = 2; i * i <= p; ++i) {
        if (!(p % i)) {
            arr.push_back((P - 1) / i);
            while (!(p % i)) p /= i;
        }
    }
    if (p != 1) arr.push_back((P - 1) / p);
}

int chk(int g) {
    for (auto x : arr) {
        if (ksm(g, x) == 1) return 0;
    }
    return 1;
}

void NTTInit() {
    divide();
    G = 2;
    while (!chk(G)) ++G;
    iG = ksm(G);
}

int tr[1 << N];

void NTT(vector<int> &f, int type = 1) {
    int n = f.size();
    printf("%d\n", n);
    for (int i = 1; i < n; ++i) tr[i] = (tr[i >> 1] >> 1) | ((i & 1) ? n >> 1 : 0);
    for (int i = 0; i < n; ++i) if (i < tr[i]) swap(f[i], f[tr[i]]);
    for (int len = 2; len <= n; len <<= 1) {
        int p = len >> 1, buf = ksm(type ? G : iG, (P - 1) / len);
        for (int i = 0; i < n; i += len) {
            int now = 1;
            for (int j = i; j < i + p; ++j) {
                int tmp = 1ll * now * f[j + p] % P;
                ((f[j + p] = f[j] - tmp) < 0) && (f[j + p] += P);
                ((f[j] += tmp) >= P) && (f[j] -= P);
                now = 1ll * now * buf % P;
            }
        }
    }
    if (!type) {
        int iv = ksm(n);
        for (int i = 0; i < n; ++i) {
            f[i] = 1ll * f[i] * iv % P;
        }
    }
}

vector<int> operator * (vector<int> x, vector<int> y) {
    int n = 1;
    while (n < (int)x.size() + (int)y.size() - 1) n <<= 1;
    x.resize(n), y.resize(n);
    NTT(x), NTT(y);
    for (int i = 0; i < n; ++i) x[i] = 1ll * x[i] * y[i] % P;
    NTT(x, 0);
    while (!x.empty() && !x.back()) x.pop_back();
    return x;
}

void preCalc() {
    NTTInit();
    for (int i = fac[0] = iFac[0] = 1; i <= (1 << N); ++i) {
        fac[i] = 1ll * fac[i - 1] * i % P;
        iFac[i] = (i == 1 ? 1 : 1ll * (P - P / i) * iFac[P % i] % P);
    }
    for (int i = 1; i <= (1 << N); ++i) {
        iFac[i] = 1ll * iFac[i - 1] * iFac[i] % P;
    }
    for (int o = 0; o < N; ++o) {
        for (int i = 0; i <= (1 << o) - 1 - (!!o); ++i) {
            f[o][o + 1][i + (1 << o)] = g[o][o + 1][i + (1 << o)] = C((1 << o) - 1 - (!!o), i);
        }
        for (int i = o + 2; i <= N; ++i) {
            vector<int> F, G, H;
            for (int j = 0; j < (1 << (i - 1)); ++j) F.push_back(f[o][i - 1][j]);
            for (int j = 0; j <= (1 << (i - 1)); ++j) G.push_back(C(1 << (i - 1), j));
            for (int j = 0; j <= (1 << (i - 1)) - 1; ++j) H.push_back(C((1 << (i - 1)) - 1, j));
            vector<int> fg = F * G, fh = F * H;
            for (int j = 0; j < (int)fg.size(); ++j) f[o][i][j] = (f[o][i][j] + fg[j]) % P;
            for (int j = 0; j < (int)fh.size(); ++j) g[o][i][j] = (g[o][i][j] + fh[j]) % P;
            for (int j = 1; j < (1 << (i - 1)); ++j) {
                f[o][i][j + (1 << (i - 1))] = (0ll + f[o][i][j + (1 << (i - 1))] + f[o][i - 1][j] + g[o][i - 1][j]) % P;
                g[o][i][j + (1 << (i - 1))] = (g[o][i][j + (1 << (i - 1))] + g[o][i - 1][j]) % P;
            }
        }
    }
}

signed main() {
    scanf("%d", &P);
    preCalc();
    int T; scanf("%d", &T);
    while (T--) {
        int k, n, p; scanf("%d%d%d", &k, &n, &p);
        int z = 0;
        while ((1 << z) < p) ++z;
        if ((1 << z) != p) {
            puts("0");
            continue;
        }
        if (p == (1 << k) && n == (1 << k)) {
            puts("1");
            continue;
        }
        printf("%d\n", f[z][k][n]);
    }
    return 0;
}