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

class CandyDrawing {
	typedef unsigned long long ull;

	unsigned long long pw(ull a, int e, ull mod) {
		if(e <= 0) return 1;
		ull x =pw(a,e/2,mod);
		x =(x*x)%mod;
		if(e%2 != 0) x =(x*a)%mod;
		return x;}

	public: int findProbability(int N, int K, int MOD) {
		ull mod =MOD;
		ull modSq =mod*mod;		
		vector< vector<ull> > A(32,vector<ull>(K+1,mod));
		vector< vector<ull> > A2 =A;
		for(int i =0; i <= 30; i++) for(int j =0; j <= K; j++) if((N>>i) < j || (N>>i) == 0) A[i][j] =0;
		for(int i =0; i <= 30; i++) A[i][0] =1;
		for(int i =0; i <= 30; i++) for(int j =0; j <= K; j++) if((N>>(i+1)) < j || (N>>i) == 0) A2[i][j] =0;
		for(int i =0; i <= 30; i++) A2[i][0] =1;

		vector<ull> inv(K+9,1);
		for(int i =1; i <= K; i++) inv[i] =pw(i,MOD-2,mod);
		vector< vector<ull> > powNs(32,vector<ull>(K+1,1));
		for(int i =0; i <= 30; i++) for(int j =1; j <= K; j++) {
			powNs[i][j] =(powNs[i][j-1]*((N>>i)+1))%mod;
			powNs[i][j] =(powNs[i][j]*inv[j])%mod;}

		for(int s =29; s >= 0; s--) for(int j =0; j <= K; j++) {

			if(A2[s][j] == mod) {
				ull decP =1;
				for(int i =0; i <= j; i++) {
					ull c =(decP*powNs[s][i])%mod;
					decP =(decP*((N>>(s+1))-j+i+1))%mod;
					if(i&1 && A2[s][j] >= 2*modSq) A2[s][j] -=2*modSq;
					if((j-i)&1) A2[s][j] +=modSq-c*A[s+1][j-i];
					else A2[s][j] +=c*A[s+1][j-i];}
				A2[s][j] %=mod;}

			if(A[s][j] == mod) {
				if((N>>s)&1) {
					for(int i =0; i < j; i++) {
						if(i&1 && A[s][j] >= 2*modSq) A[s][j] -=2*modSq;
						A[s][j] +=A[s+1][i]*A2[s][j-i-1];}
					A[s][j] %=mod;
					A[s][j] =(A[s][j]*((N>>(s+1))+1))%mod;}
				for(int i =0; i <= j; i++) {
					if(i&1 && A[s][j] >= 2*modSq) A[s][j] -=2*modSq;
					A[s][j] +=A[s+1][i]*A2[s][j-i];}
				A[s][j] %=mod;}
			}
		
		return A[0][K];}
	};