Problem Description

For a non-negative integer sequence \( a \), define its corresponding independent set sequence \( f(a) \):

• Suppose \( a_i \) is changed to \( 0 \), and we select several numbers that are not adjacent to each other such that their sum is maximized. Then \( f(a)_i \) represents the maximum sum.

Given \( n, m \), find how many non-negative integer sequences \( b \) of length \( b \) satisfy the following condition:

• There exists at least one non-negative integer sequence \( a \) of length \( n \) and range \([0, m]\) such that \( f(a) = b \).

The answer should be taken modulo the given prime number \( \textit{MOD} \).

Input Format

A single line containing three numbers: \( n, m, \textit{MOD} \).

Output Format

A single line containing one number, representing the answer.

Sample Input and Output

Sample Input #1

3 1 1000000007

Sample Output #1

6

Sample Input #2

4 2 1000000007

Sample Output #2

47

Sample Input #3

20 24 1000000007

Sample Output #3

901565358

Sample Input #4

123 234 1000000009

Sample Output #4

141754844

Sample Input #5

1234 2345 1004535809

Sample Output #5

576196526

Notes

This problem uses subtask-based testing.

For \( 100\% \) of the data, \( 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 a prime number.

• Subtask 1 (10%): \( n, m \leq 5 \).
• Subtask 2 (15%): \( n \leq 300 \), \( m = 1 \).
• Subtask 3 (25%): \( n \leq 300 \), \( m \leq 5 \).
• Subtask 4 (20%): \( n, m \leq 50 \).
• Subtask 5 (15%): \( n, m \leq 300 \).
• Subtask 6 (15%): No special restrictions.

见题面 Input 部分

见题面 Output 部分