#include<bits/stdc++.h>
using namespace std;
namespace Polynomial
{
	using ll=long long;
	using poly=vector<ll>;
	ll mod=998244353,pr=3;
	ll ksm(ll a,ll b)
	{
		ll ans=1;
		while(b)
		{
			if(b&1) ans=ans*a%mod;
			b>>=1;
			a=a*a%mod;
		}
		return ans;
	}
	inline int sz(const poly &p)
	{
		return p.size();
	}
	const poly operator +(const poly &a,const poly &b)
	{
		int p=sz(a),q=sz(b);
		int n=max(p,q);
		poly ret(n,0);
		for(int i=0;i<n;i++)
		{
			if(i<p) ret[i]+=a[i];
			if(i<q) ret[i]+=b[i];
			if(ret[i]>=mod) ret[i]-=mod;
		}
		return ret;
	}
	const poly operator -(const poly &a,const poly &b)
	{
		int p=sz(a),q=sz(b);
		int n=max(p,q);
		poly ret(n,0);
		for(int i=0;i<n;i++)
		{
			if(i<p) ret[i]+=a[i];
			if(i<q) ret[i]+=mod-b[i];
			if(ret[i]>=mod) ret[i]-=mod;
		}
		return ret;
	}
	poly operator *(poly a,poly b)
	{
		const ll g=pr;
		int len=sz(a)+sz(b);
		int m=1;
		while(m<sz(a)+sz(b)) m*=2;
		a.resize(m);
		b.resize(m);
		vector<int> rev(m);
		for(int i=0;i<m;i++)
			rev[i]=(rev[i>>1]>>1)|((i&1)*(m>>1));
		for(int i=0;i<m;i++)
			if(rev[i]<i)
			{
				swap(a[i],a[rev[i]]);
				swap(b[i],b[rev[i]]);
			}
		for(int i=1;i<m;i<<=1)
		{
			ll gn=ksm(g,(mod-1)/i/2);
			for(int j=0;j<m;j+=(i<<1))
			{
				ll g0=1;
				for(int k=0;k<i;k++,g0=g0*gn%mod)
				{
					{
						ll x=a[j+k],y=g0*a[i+j+k]%mod;
						a[j+k]=(x+y)%mod;
						a[i+j+k]=(x+mod-y)%mod;
					}
					{
						ll x=b[j+k],y=g0*b[i+j+k]%mod;
						b[j+k]=(x+y)%mod;
						b[i+j+k]=(x+mod-y)%mod;
					}
				}
			}
		}
		for(int i=0;i<m;i++)
			a[i]=a[i]*b[i]%mod;
		for(int i=0;i<m;i++)
			if(rev[i]<i)
				swap(a[i],a[rev[i]]);
		for(int i=1;i<m;i<<=1)
		{
			ll gn=ksm(g,(mod-1)/i/2*(mod-2));
			for(int j=0;j<m;j+=(i<<1))
			{
				ll g0=1;
				for(int k=0;k<i;k++,g0=g0*gn%mod)
				{
					ll x=a[j+k],y=g0*a[i+j+k]%mod;
					a[j+k]=(x+y)%mod;
					a[i+j+k]=(x+mod-y)%mod;
				}
			}
		}
		ll val=ksm(m,mod-2);
		for(int i=0;i<m;i++)
			a[i]=a[i]*val%mod;
		a.resize(len-1);
		return a;
	}
	poly inv(poly p,int deg)
	{
		p.resize(deg);
		if(deg==1) return {ksm(p[0],mod-2)};
		poly w=inv(p,(deg+1)/2);
		poly g=w+w-p*w*w;
		g.resize(deg);
		return g;
	}
	poly deriv(poly p)
	{
		for(int i=0;i<sz(p);i++)
			p[i]=p[i]*i%mod;
		p.erase(p.begin());
		return p;
	}
	poly integ(poly p)
	{
		p.insert(p.begin(),0);
		for(int i=0;i<sz(p);i++)
			p[i]=p[i]*ksm(i,mod-2)%mod;
		return p;
	}
	poly ln(poly p)
	{
		return integ(deriv(p)*inv(p,sz(p)));
	}
	poly exp(poly p,int deg)
	{
		p.resize(deg);
		if(deg==1)
			return {1};
		poly g=exp(p,(deg+1)/2);
		g=g*(poly{1}-ln(g)+p);
		g.resize(deg);
		return g;
	}
	const poly operator %(poly a,poly b)
	{
		if(sz(a)<sz(b)) return a;
		int n=sz(a),m=sz(b);
		int d=n-m+1;
		poly a2=a,b2=b;
		reverse(a2.begin(),a2.end());
		reverse(b2.begin(),b2.end());
		a2.resize(d);
		b2.resize(d);
		poly q=a2*inv(b2,d);
		q.resize(d);
		reverse(q.begin(),q.end());
		q=a-b*q;
		q.resize(m-1);
		return q;
	}
	const poly operator /(poly a,poly b)
	{
		if(sz(a)<sz(b)) return a;
		int n=sz(a),m=sz(b);
		int d=n-m+1;
		poly a2=a,b2=b;
		reverse(a2.begin(),a2.end());
		reverse(b2.begin(),b2.end());
		a2.resize(d);
		b2.resize(d);
		poly q=a2*inv(b2,d);
		q.resize(d);
		reverse(q.begin(),q.end());
		return q;
	}
	void init()
	{
		ll val=mod-1,tmp=mod-1;
		vector<ll> vec;
		for(int i=2;i*i<=tmp;i++)
			if(tmp%i==0)
			{
				vec.push_back(val/i);
				while(tmp%i==0) tmp/=i;
			}
		if(tmp>1) vec.push_back(val/tmp);
		for(pr=2;;pr++)
		{
			int ok=1;
			for(auto x:vec)
				if(ksm(pr,x)==1)
					ok=0;
			if(ok) break;
		}
	}
}
using namespace Polynomial;
poly f[19][19],g[19][19];
ll fact[1001000],rfact[1001000];
ll C(int n,int k)
{
	if(k<0||k>n) return 0;
	return fact[n]*rfact[k]%mod*rfact[n-k]%mod;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>mod;
	fact[0]=1;
	for(int i=1;i<1001000;i++)
		fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<1001000;i++)
		rfact[i]=ksm(fact[i],mod-2);
	init();
	f[1][0]={0,1};
	g[1][0]={0,1};
	auto mv=[&](const poly &a,int deg)
	{
		poly ret=a;
		reverse(ret.begin(),ret.end());
		while(deg--) ret.push_back(0);
		reverse(ret.begin(),ret.end());
		return ret;
	};
	for(int i=2;i<=17;i++)
	{
		// 情况一：左边没有满
		poly tmp((1<<i-1)+1);
		for(int j=0;j<sz(tmp);j++)
			tmp[j]=C(1<<i-1,j);
		for(int x=0;x<i;x++)
			f[i][x]=f[i-1][x]*tmp;
		for(int j=0;j<sz(tmp);j++)
			tmp[j]=C((1<<i-1)-1,j);
		for(int x=0;x<i;x++)
			g[i][x]=f[i-1][x]*tmp;
		// 情况二：左边满了，且有 2^{i-1}
		for(int x=0;x<i;x++)
			f[i][x]=f[i][x]+mv(f[i-1][x],1<<i-1);
		for(int x=0;x<i;x++)
			g[i][x]=g[i][x]+mv(g[i-1][x],1<<i-1);
		// 情况三：左边满了，且没 2^{i-1}，且没 2^i-1
		for(int j=0;j<sz(tmp);j++)
			tmp[j]=C((1<<i-1)-2,j);
		f[i][i-1]=f[i][i-1]+mv(tmp,1<<i-1);
		g[i][i-1]=g[i][i-1]+mv(tmp,1<<i-1);
		// 情况四：左边满了，且没 2^{i-1}，且有 2^i-1
		for(int x=0;x<i;x++)
			f[i][x]=f[i][x]+mv(g[i-1][x],1<<i-1);
	}
	int t;
	cin>>t;
	while(t--)
	{
		int k,n,p;
		cin>>k>>n>>p;
		if(__builtin_popcount(p)>1)
		{
			cout<<"0\n";
			continue;
		}
		p=__lg(p);
		if(n==(1<<k))
		{
			if(p==k+1)
				cout<<"1\n";
			else
				cout<<"0\n";
			continue;
		}
		cout<<f[k][p][n]<<'\n';
	}
	return 0;
}