#line 5 "CandyDrawing.cpp"
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <utility>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forl(i, n) for (int i = 1; i <= int(n); i++)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
#define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define mp(x, y) make_pair((x), (y))
#define ft first
#define sc second
#define x first
#define y second
#define isnan(a) false
#define isinf(a) false

using namespace std;

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;

class CandyDrawing
{
	public:
	int findProbability(int N, int K, int MOD);
};

li gcd(li a, li b, li& x, li& y)
{
	if (a == 0)
	{
		x = 0, y = 1;
		return b;
	}
	
	li xx, yy, g = gcd(b % a, a, xx, yy);
	x = yy - b / a * xx;
	y = xx;
	return g;
}

li inv(li a, li mod)
{
	li x, y;
	assert(gcd(a, mod, x, y) == 1);
	return (x % mod + mod) % mod;
}

int mod;
li bmod;

inline int add(int a, int b) { return int((a + 0ll + b) % mod); }
inline int sub(int a, int b) { return add(a, mod - b); }
inline int mul(int a, int b) { return int((a * 1ll * b) % mod); }

const int MAXK = 2000 + 3, LOGN = 32;

int z[2][MAXK];
int p[2][MAXK];
int C[MAXK];
int invc[MAXK];
int cc[MAXK];
int cc1[MAXK];
int cc2[MAXK];

inline li smul(li a, li b)
{
	li q = li(ld(a) * b / bmod);
	li ans = (a * b - q * bmod) % bmod;
	return ans < 0 ? ans + bmod : ans;
}

int CandyDrawing::findProbability(int N, int K, int MOD)
{
	mod = MOD;
	bmod = MOD * 2300000000ll;
	
	vector<int> nn;
	{
    	int n = N;
    	while (n) nn.pb(n), n >>= 1;
    	reverse(all(nn));
	}
	
	forl(i, MAXK - 1) invc[i] = int(inv(i, mod));
	
	memset(z, 0, sizeof(z));
	memset(p, 0, sizeof(p));
	
	z[0][0] = 1;
	z[0][1] = 1;
	forl(ii, sz(nn) - 1)
	{
		int cur = ii & 1;
		int prev = cur ^ 1;
		
		int n = nn[ii];
		int n2 = n / 2;
		
		forn(i, K + 1) cc[i] = mul(invc[i], n + 1);
		forn(i, K + 1) cc1[i] = mul(n2 - i + 1, cc[i]);
		forn(i, K + 1) cc2[i] = mul(i, cc[i]);
		
		forn(k, K + 1)
		{
			if (k > n2) continue;
			
			if (k > 0)
				forn(i, k + 1)
				{
					cc1[i] -= cc[i];
					(cc1[i] < 0) && (cc1[i] += mod);
				}
			
			li dv = 0;
			int q = 1;
			ford(i, k + 1)
			{
				if (i < k)
				{
					int c = cc1[k - i] - mod + cc2[k - i];
					(c < 0) && (c += mod);
					q = mul(q, c);
				}
				
				if (i & 1)
				{
					dv += bmod - q * 1ll * z[prev][i];
					(dv >= bmod) && (dv -= bmod);
				}
				else
				{
					dv += q * 1ll * z[prev][i];
					(dv >= bmod) && (dv -= bmod);
				}
			}
			p[cur][k] = int(dv % mod);
		}
		
		li pp = 0;
		forn(k, K + 1)
		{
			if (k > n) continue;
			
			li dv = 0;
			
			forn(i, k + 1)
			{
				dv += z[prev][i] * 1ll * p[cur][k - i];
				(dv >= bmod) && (dv -= bmod);
			}
			
			li odv = dv;
			if (n & 1) dv = (dv + pp % mod * ((n + 1) / 2)) % mod;
			pp = odv;
			
			z[cur][k] = int(dv % mod);
		}
	}
	
	return z[(sz(nn) - 1) & 1][K];
}