For a sequence of non-negative integers $a$, we define its corresponding independent set sequence $f(a)$ as follows:
- Suppose we change $a_i$ to $0$. We then choose a subset of elements such that no two elements are adjacent, maximizing their sum. $f(a)_i$ denotes this maximum sum.
Given $n$ and $m$, find the number of non-negative integer sequences $b$ of length $n$ that 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$.
The answer should be modulo the given prime $MOD$.
Input
A single line containing three integers $n, m, MOD$.
Output
A single line containing one integer, the answer.
Examples
Input 1
3 1 1000000007
Output 1
6
Input 2
4 2 1000000007
Output 2
47
Input 3
20 24 1000000007
Output 3
901565358
Input 4
123 234 1000000009
Output 4
141754844
Input 5
1234 2345 1004535809
Output 5
576196526
Constraints
This problem uses subtask-based testing.
For 100% of the data, $1 \le n, m \le 3 \times 10^3$, $n \ge 2$, $10^9 < MOD < 1.01 \times 10^9$, and $MOD$ is a prime number.
- Subtask 1 (10%): $n, m \le 5$.
- Subtask 2 (15%): $n \le 300$, $m = 1$.
- Subtask 3 (25%): $n \le 300$, $m \le 5$.
- Subtask 4 (20%): $n, m \le 50$.
- Subtask 5 (15%): $n, m \le 300$.
- Subtask 6 (15%): No additional constraints.