Problem Description

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}$.

Input Format

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

Output Format

A single line with one number, the answer.

3 1 1000000007

6

4 2 1000000007

47

20 24 1000000007

901565358

123 234 1000000009

141754844

1234 2345 1004535809

576196526

Hint

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