P10082 [GDKOI2024 Senior] Chicken

For a non-negative integer sequence $a$, define its corresponding independent set sequence $f(a)$: - Suppose we change $a_i$ to $0$. Then we choose some numbers that are pairwise non-adjacent so that their sum is as large as possible. Let $f(a)_i$ be this maximum sum. Now given $n, m$, determine how many non-negative integer sequences $b$ of length $n$ satisfy the following condition: - There exists at least one non-negative integer sequence $a$ of length $n$ with values in $[0, m]$ such that $f(a) = b$. Output the answer modulo the given prime $\textit{MOD}$.

A single line with three numbers $n, m, \textit{MOD}$.

A single line with one number, the answer.

**This problem uses bundled subtask tests.** For $100\%$ of the testdata, $1 \leq n, m \leq 3 \times 10^3$, $n \geq 2$, $10^9 < \textit{MOD} < 1.01 \times 10^9$, and $\textit{MOD}$ is prime. - Subtask 1 (10%): $n, m \leq 5$. - Subtask 2 (15%): $n \leq 300$, $m = 1$. - Subtask 3 (25%): $n \leq 300$, $m ≤ 5$. - Subtask 4 (20%): $n, m \leq 50$. - Subtask 5 (15%): $n, m \leq 300$. - Subtask 6 (15%): No special constraints. Translated by ChatGPT 5