{"raw_statement":[{"iden":"problem statement","content":"You are given an integer $N$ and prime $P$.\nWe call a sequence of $N$ intervals $([L_1,R_1] ,[L_2,R_2], \\cdots, [L_N,R_N])$ **good** if and only if both of the followings are satisfied:\n\n*   $1\\le L_i\\le R_i\\le N$ holds for all $1\\le i\\le N$.\n*   There exists a **unique** permutation $x=(x_1,x_2,\\cdots,x_N)$ of $(1,2,\\cdots,N)$ such that $L_i\\le x_i\\le R_i$ holds for all $1\\le i\\le N$.\n\nCount the number, modulo $P$, of **good** sequences of intervals."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 5000$\n*   $10^9<P<1.01\\times 10^9$\n*   $P$ is prime.\n*   All input values are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $P$"},{"iden":"sample input 1","content":"2 1005488041"},{"iden":"sample output 1","content":"6\n\nThe following $6$ sequences are good:\n\n*   $([1,1],[2,2])$\n*   $([1,2],[2,2])$\n*   $([1,1],[1,2])$\n*   $([2,2],[1,1])$\n*   $([2,2],[1,2])$\n*   $([1,2],[1,1])$"},{"iden":"sample input 2","content":"5 1005488041"},{"iden":"sample output 2","content":"102960"},{"iden":"sample input 3","content":"100 1005488041"},{"iden":"sample output 3","content":"47599495"},{"iden":"sample input 4","content":"1000 1005488041"},{"iden":"sample output 4","content":"632708165"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}