{"problem":{"name":"Unique Matching","description":{"content":"You are given an integer $N$ and prime $P$. We 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: *   $1\\le L_i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc067_d"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $2 \\leq N \\leq 5000$\n*   $10^9<P<1.01\\times 10^9$\n*   $P$ is prime.\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $P$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc067_d","tags":[],"sample_group":[["2 1005488041","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])$"],["5 1005488041","102960"],["100 1005488041","47599495"],["1000 1005488041","632708165"]],"created_at":"2026-03-03 11:01:14"}}