#include <bits/stdc++.h>

using namespace std;

const int N = 11;

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

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

void preCalc() {
    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) {
        if (o != N) {
            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 + 1; i <= N; ++i) {
            for (int j = (1 << o); j < (1 << (i - 1)); ++j) {
                for (int k = 0; k <= (1 << (i - 1)); ++k) {
                    f[o][i][j + k] = (f[o][i][j + k] + 1ll * f[o][i - 1][j] * C((1 << (i - 1)), k)) % P;
                    if (k != (1 << (i - 1))) g[o][i][j + k] = (g[o][i][j + k] + 1ll * f[o][i - 1][j] * C((1 << (i - 1)) - 1, k)) % 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;
        }
        printf("%d\n", f[z][k][n]);
    }
    return 0;
}