{"problem":{"name":"Weird LIS","description":{"content":"You are given integers $N$ and $M$. Find the number of arrays $A=[A_1, A_2, \\ldots, A_N]$ of length $N$ such that the following conditions hold: *   $2 \\le A_i \\le M$ ($1 \\leq i \\leq N$) *   There ex","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc055_c"},"statements":[{"statement_type":"Markdown","content":"You are given integers $N$ and $M$. Find the number of arrays $A=[A_1, A_2, \\ldots, A_N]$ of length $N$ such that the following conditions hold:\n\n*   $2 \\le A_i \\le M$ ($1 \\leq i \\leq N$)\n*   There exists a permutation $P=[P_1,P_2,\\ldots,P_N]$ of integers from $1$ to $N$ with the following property:\n    *   For every $i$ from $1$ to $N$, $A_i$ equals the length of the longest increasing subsequence of the sequence $[P_1, P_2, \\ldots, P_{i-1}, P_{i+1}, \\ldots, P_{N-1}, P_N]$.\n\nAs this number can be very large, output it modulo some prime $Q$.\n\n## Constraints\n\n*   $3 \\le N \\le 5000$.\n*   $2 \\le M \\le N-1$.\n*   $10^8 \\le Q \\le 10^9$\n*   $Q$ is a prime.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc055_c","tags":[],"sample_group":[["3 2 686926217","1\n\nThe only such array is $[2, 2, 2]$, for which exists a permutation $[1, 2, 3]$."],["4 3 354817471","9\n\nThere are $9$ such arrays: $[2, 2, 2, 2]$, $[2, 2, 2, 3]$, $[2, 2, 3, 2]$, $[2, 2, 3, 3]$, $[2, 3, 2, 2]$, $[2, 3, 3, 2]$, $[3, 2, 2, 2]$, $[3, 3, 2, 2]$, $[3, 3, 3, 3]$."],["5 2 829412599","1\n\nThe only such array is $[2, 2, 2, 2, 2]$."],["5 3 975576997","23"],["69 42 925171057","801835311"]],"created_at":"2026-03-03 11:01:14"}}