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

namespace PolyNTT{
    int PMod=998244353,PG=3;
    typedef long long ll;
    
    int qpow(int x,ll y) {
        int z=1;
        for(;y;y>>=1) {
            if(y&1) z=1ll*z*x%PMod;
            x=1ll*x*x%PMod;
        }
        return z;
    }
    
    void NTT(vector<ll> &a,int len,int op) {
        static vector<int> rev,W;
        rev.resize(len),W.resize(len);
        for(int i=1;i<len;i++) rev[i]=(rev[i>>1]>>1)|(i&1? len>>1:0);
        for(int i=1;i<len;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
        for(int h=2,p=1;h<=len;p=h,h<<=1) {
            W[0]=1,W[1]=qpow(PG,(PMod-1)/h);
            if(op==-1) W[1]=qpow(W[1],h-1);
            for(int i=2;i<p;i++) W[i]=1ll*W[i-1]*W[1]%PMod;
            for(int i=0;i<len;i+=h) {
                for(int j=i;j<i+p;j++) {
                    ll u=a[j],v=1ll*W[j-i]*a[j+p]%PMod;
                    a[j]=u+v,a[j+p]=u-v;
                }
            }
        }
        for(int i=0;i<len;i++) a[i]=(a[i]%PMod+PMod)%PMod;
        if(op==-1) {
            int inv=qpow(len,PMod-2);
            for(int i=0;i<len;i++) a[i]=1ll*a[i]*inv%PMod;
        }
    }
    
    typedef vector<ll> Poly;
    
    Poly operator+(Poly x,Poly y) {
        x.resize(max(x.size(),y.size()));
        for(int i=0;i<y.size();i++) x[i]+=y[i];
        return x;
    }

    Poly upd(Poly x) {
        for(int i=0;i<x.size();i++) x[i]=(x[i]%PMod+PMod)%PMod;
        return x;
    }
    
    Poly operator*(Poly x,Poly y) {
        int l=1,ll=x.size()+y.size()-1;
        while(l<ll) l<<=1;
        x.resize(l),y.resize(l);
        NTT(x,l,1),NTT(y,l,1);
        for(int i=0;i<l;i++) x[i]=1ll*x[i]*y[i]%PMod;
        NTT(x,l,-1);
        x.resize(ll);
        return x;
    }

    Poly Shift(Poly x,int s) {
        if(x.size()+s<=0) return {};
        if(!s) return x;
        if(s>0) {
            x.resize(x.size()+s);
            for(int i=x.size()-1;i>=0;i--) x[i]=i<s? 0:x[i-s];
        }
        else {
            for(int i=0;i<x.size();i++) x[i]=i-s<x.size()? x[i-s]:0;
            x.resize(x.size()+s);
        }
        return x;
    }
}using namespace PolyNTT;

const int N=20;
const int M=1<<17|10;

int T,Mod;
int lg[M];
Poly f[N][N],g[N][N];
int fac[M],inv[M];

int lowbit(int x) {
    return x&-x;
}

int C(int x,int y) {
    if(x<y || y<0) return 0;
    return 1ll*fac[x]*inv[y]%Mod*inv[x-y]%Mod;
}

bool chkg(int g) {
    int x=Mod-1;
    for(int i=2;i*i<=x;i++) {
        if(x%i) continue;
        if(qpow(g,(Mod-1)/i)==1) return 0;
        while(x%i==0) x/=i;
    }
    if(x>1) {
        if(qpow(g,(Mod-1)/x)==1) return 0;
    }
    return 1;
}

int main() {
    scanf("%d%d",&Mod,&T);
    PMod=Mod;
    PG=2;
    while(!chkg(PG)) PG++;
    int n=M-10;
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%Mod;
    inv[n]=qpow(fac[n],Mod-2);
    for(int i=n-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%Mod;
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    f[1][0]=g[1][0]={0,1};
    for(int i=2;i<=17;i++) {
        for(int j=0;j<i;j++) f[i][j].resize(1<<i),g[i][j].resize(1<<i);
        Poly p;
        p.resize((1<<i-1)+1);
        for(int j=0;j<=1<<i-1;j++) p[j]=C(1<<i-1,j);
        for(int j=0;j<i-1;j++) f[i][j]=f[i][j]+f[i-1][j]*p;
        for(int j=0;j<=1<<i-1;j++) p[j]=C((1<<i-1)-1,j);
        for(int j=0;j<i-1;j++) g[i][j]=g[i][j]+f[i-1][j]*p;
        for(int j=0;j<i;j++) f[i][j]=f[i][j]+Shift(f[i-1][j],1<<i-1),g[i][j]=g[i][j]+Shift(g[i-1][j],1<<i-1);
        for(int j=0;j<(1<<i-1)-1;j++) f[i][i-1][j+(1<<i-1)]+=C((1<<i-1)-2,j),g[i][i-1][j+(1<<i-1)]+=C((1<<i-1)-2,j);
        for(int j=0;j<i;j++) f[i][j]=f[i][j]+Shift(g[i-1][j],1<<i-1);
        for(int j=0;j<i;j++) f[i][j]=upd(f[i][j]);
    }
    while(T--) {
        int k,n,m;
        scanf("%d%d%d",&k,&n,&m);
        if(lowbit(m)!=m) printf("0\n");
        else if(n==(1<<k)) printf("%d\n",m==(1<<k));
        else printf("%d\n",n<f[k][lg[m]].size()? f[k][lg[m]][n]:0);
    }
    return 0;
}