#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] ;
}
I2xpbmUgNSAiQ2FuZHlEcmF3aW5nLmNwcCIKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxudW1lcmljPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHF1ZXVlPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxjc3RkbGliPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0cmluZz4KI2luY2x1ZGUgPGN0aW1lPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjYXNzZXJ0PgojaW5jbHVkZSA8Y2xpbWl0cz4KCiNkZWZpbmUgZm9ybihpLCBuKSBmb3IgKGludCBpID0gMDsgaSA8IGludChuKTsgaSsrKQojZGVmaW5lIGZvcmwoaSwgbikgZm9yIChpbnQgaSA9IDE7IGkgPD0gaW50KG4pOyBpKyspCiNkZWZpbmUgZm9yZChpLCBuKSBmb3IgKGludCBpID0gaW50KG4pIC0gMTsgaSA+PSAwOyBpLS0pCiNkZWZpbmUgZm9yZShpLCBsLCByKSBmb3IgKGludCBpID0gaW50KGwpOyBpIDw9IGludChyKTsgaSsrKQojZGVmaW5lIGNvcnJlY3QoeCwgeSwgbiwgbSkgKDAgPD0gKHgpICYmICh4KSA8IChuKSAmJiAwIDw9ICh5KSAmJiAoeSkgPCAobSkpCiNkZWZpbmUgYWxsKGEpIChhKS5iZWdpbigpLCAoYSkuZW5kKCkKI2RlZmluZSBzeihhKSBpbnQoKGEpLnNpemUoKSkKI2RlZmluZSBwYihhKSBwdXNoX2JhY2soYSkKI2RlZmluZSBtcCh4LCB5KSBtYWtlX3BhaXIoKHgpLCAoeSkpCiNkZWZpbmUgZnQgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKI2RlZmluZSB4IGZpcnN0CiNkZWZpbmUgeSBzZWNvbmQKI2RlZmluZSBpc25hbihhKSBmYWxzZQojZGVmaW5lIGlzaW5mKGEpIGZhbHNlCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGk7CnR5cGVkZWYgbG9uZyBkb3VibGUgbGQ7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gcHQ7Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBYPiBpbmxpbmUgWCBhYnMoY29uc3QgWCYgYSkgeyByZXR1cm4gYSA8IDA/IC1hOiBhOyB9CnRlbXBsYXRlPHR5cGVuYW1lIFg+IGlubGluZSBYIHNxcihjb25zdCBYJiBhKSB7IHJldHVybiBhICogYTsgfQoKY29uc3QgaW50IElORiA9IGludCgxZTkpOwpjb25zdCBsaSBJTkY2NCA9IGxpKDFlMTgpOwpjb25zdCBsZCBFUFMgPSAxZS05LCBQSSA9IDMuMTQxNTkyNjUzNTg5NzkzMjM4NDYyNjQzMzgzMjc5NTsKCmNsYXNzIENhbmR5RHJhd2luZwp7CglwdWJsaWM6CglpbnQgZmluZFByb2JhYmlsaXR5KGludCBOLCBpbnQgSywgaW50IE1PRCk7Cn07CgpsaSBnY2QobGkgYSwgbGkgYiwgbGkmIHgsIGxpJiB5KQp7CglpZiAoYSA9PSAwKQoJewoJCXggPSAwLCB5ID0gMTsKCQlyZXR1cm4gYjsKCX0KCQoJbGkgeHgsIHl5LCBnID0gZ2NkKGIgJSBhLCBhLCB4eCwgeXkpOwoJeCA9IHl5IC0gYiAvIGEgKiB4eDsKCXkgPSB4eDsKCXJldHVybiBnOwp9CgpsaSBpbnYobGkgYSwgbGkgbW9kKQp7CglsaSB4LCB5OwoJYXNzZXJ0KGdjZChhLCBtb2QsIHgsIHkpID09IDEpOwoJcmV0dXJuICh4ICUgbW9kICsgbW9kKSAlIG1vZDsKfQoKaW50IG1vZDsKbGkgYm1vZDsKCmlubGluZSBpbnQgYWRkKGludCBhLCBpbnQgYikgeyByZXR1cm4gaW50KChhICsgMGxsICsgYikgJSBtb2QpOyB9CmlubGluZSBpbnQgc3ViKGludCBhLCBpbnQgYikgeyByZXR1cm4gYWRkKGEsIG1vZCAtIGIpOyB9CmlubGluZSBpbnQgbXVsKGludCBhLCBpbnQgYikgeyByZXR1cm4gaW50KChhICogMWxsICogYikgJSBtb2QpOyB9Cgpjb25zdCBpbnQgTUFYSyA9IDIwMDAgKyAzLCBMT0dOID0gMzI7CgppbnQgelsyXVtNQVhLXTsKaW50IHBbMl1bTUFYS107CmludCBDW01BWEtdOwppbnQgaW52Y1tNQVhLXTsKaW50IGNjW01BWEtdOwppbnQgY2MxW01BWEtdOwppbnQgY2MyW01BWEtdOwoKaW5saW5lIGxpIHNtdWwobGkgYSwgbGkgYikKewoJbGkgcSA9IGxpKGxkKGEpICogYiAvIGJtb2QpOwoJbGkgYW5zID0gKGEgKiBiIC0gcSAqIGJtb2QpICUgYm1vZDsKCXJldHVybiBhbnMgPCAwID8gYW5zICsgYm1vZCA6IGFuczsKfQoKaW50IENhbmR5RHJhd2luZzo6ZmluZFByb2JhYmlsaXR5KGludCBOLCBpbnQgSywgaW50IE1PRCkKewoJbW9kID0gTU9EOwoJYm1vZCA9IE1PRCAqIDIzMDAwMDAwMDBsbDsKCQoJdmVjdG9yPGludD4gbm47Cgl7CiAgICAJaW50IG4gPSBOOwogICAgCXdoaWxlIChuKSBubi5wYihuKSwgbiA+Pj0gMTsKICAgIAlyZXZlcnNlKGFsbChubikpOwoJfQoJCglmb3JsKGksIE1BWEsgLSAxKSBpbnZjW2ldID0gaW50KGludihpLCBtb2QpKTsKCQoJbWVtc2V0KHosIDAsIHNpemVvZih6KSk7CgltZW1zZXQocCwgMCwgc2l6ZW9mKHApKTsKCQoJelswXVswXSA9IDE7Cgl6WzBdWzFdID0gMTsKCWZvcmwoaWksIHN6KG5uKSAtIDEpCgl7CgkJaW50IGN1ciA9IGlpICYgMTsKCQlpbnQgcHJldiA9IGN1ciBeIDE7CgkJCgkJaW50IG4gPSBubltpaV07CgkJaW50IG4yID0gbiAvIDI7CgkJCgkJZm9ybihpLCBLICsgMSkgY2NbaV0gPSBtdWwoaW52Y1tpXSwgbiArIDEpOwoJCWZvcm4oaSwgSyArIDEpIGNjMVtpXSA9IG11bChuMiAtIGkgKyAxLCBjY1tpXSk7CgkJZm9ybihpLCBLICsgMSkgY2MyW2ldID0gbXVsKGksIGNjW2ldKTsKCQkKCQlmb3JuKGssIEsgKyAxKQoJCXsKCQkJaWYgKGsgPiBuMikgY29udGludWU7CgkJCQoJCQlpZiAoayA+IDApCgkJCQlmb3JuKGksIGsgKyAxKQoJCQkJewoJCQkJCWNjMVtpXSAtPSBjY1tpXTsKCQkJCQkoY2MxW2ldIDwgMCkgJiYgKGNjMVtpXSArPSBtb2QpOwoJCQkJfQoJCQkKCQkJbGkgZHYgPSAwOwoJCQlpbnQgcSA9IDE7CgkJCWZvcmQoaSwgayArIDEpCgkJCXsKCQkJCWlmIChpIDwgaykKCQkJCXsKCQkJCQlpbnQgYyA9IGNjMVtrIC0gaV0gLSBtb2QgKyBjYzJbayAtIGldOwoJCQkJCShjIDwgMCkgJiYgKGMgKz0gbW9kKTsKCQkJCQlxID0gbXVsKHEsIGMpOwoJCQkJfQoJCQkJCgkJCQlpZiAoaSAmIDEpCgkJCQl7CgkJCQkJZHYgKz0gYm1vZCAtIHEgKiAxbGwgKiB6W3ByZXZdW2ldOwoJCQkJCShkdiA+PSBibW9kKSAmJiAoZHYgLT0gYm1vZCk7CgkJCQl9CgkJCQllbHNlCgkJCQl7CgkJCQkJZHYgKz0gcSAqIDFsbCAqIHpbcHJldl1baV07CgkJCQkJKGR2ID49IGJtb2QpICYmIChkdiAtPSBibW9kKTsKCQkJCX0KCQkJfQoJCQlwW2N1cl1ba10gPSBpbnQoZHYgJSBtb2QpOwoJCX0KCQkKCQlsaSBwcCA9IDA7CgkJZm9ybihrLCBLICsgMSkKCQl7CgkJCWlmIChrID4gbikgY29udGludWU7CgkJCQoJCQlsaSBkdiA9IDA7CgkJCQoJCQlmb3JuKGksIGsgKyAxKQoJCQl7CgkJCQlkdiArPSB6W3ByZXZdW2ldICogMWxsICogcFtjdXJdW2sgLSBpXTsKCQkJCShkdiA+PSBibW9kKSAmJiAoZHYgLT0gYm1vZCk7CgkJCX0KCQkJCgkJCWxpIG9kdiA9IGR2OwoJCQlpZiAobiAmIDEpIGR2ID0gKGR2ICsgcHAgJSBtb2QgKiAoKG4gKyAxKSAvIDIpKSAlIG1vZDsKCQkJcHAgPSBvZHY7CgkJCQoJCQl6W2N1cl1ba10gPSBpbnQoZHYgJSBtb2QpOwoJCX0KCX0KCQoJcmV0dXJuIHpbKHN6KG5uKSAtIDEpICYgMV1bS107Cn0=