Problem Background

This problem is not a polynomial problem. It is recommended to solve problem E first.

Problem Description

Little L encountered a classic problem: given an integer sequence \(a\) of length \(n\), you need to select a non-decreasing real sequence \(b\) to minimize \(\sum_{i=1}^n |a_i - b_i|\). It can be proven that the answer is an integer.

He immediately solved this problem: isn't this just the isotonic regression template?

He found the problem too easy and decided to enhance it:

For all integer sequences \(a\) of length \(n\) where \(\forall i \in [1, n], a_i \in [1, m]\), calculate the sum of the answers to the above problem modulo a prime number \(p\). Here, \(n, m, p\) are given constants.

Now Little L is stumped. To avoid revealing that he doesn't know how to solve it, he randomly set a data range and threw the problem at you.

The pressure is now on you. Can you successfully solve this problem?

Input Format

A single line containing three integers \(n, m, p\) in sequence.

Output Format

A single line containing one integer, representing the answer.

Sample Input and Output

Sample Input #1

3 2 1000000007

Sample Output #1

4

Sample Input #2

5 5 1000000007

Sample Output #2

11040

Sample Input #3

50 50 1000000009

Sample Output #3

875463033

Notes

For \(100\%\) of the data, \(1 \le n \le 5 \times 10^3\), \(1 \le m \le 10^9\), \(10^9 < p \le 1.01 \times 10^9\), and \(p\) is guaranteed to be a prime number.

• \(\text{Subtask} 1(10\%)\): \(n, m \le 7\).
• \(\text{Subtask} 2(10\%)\): \(m \le 2\).
• \(\text{Subtask} 3(10\%)\): \(n, m \le 50\).
• \(\text{Subtask} 4(10\%)\): \(n \le 50\).
• \(\text{Subtask} 5(10\%)\): \(n, m \le 500\).
• \(\text{Subtask} 6(10\%)\): \(n \le 500\).
• \(\text{Subtask} 7(10\%)\): \(m \le 5 \times 10^3\).
• \(\text{Subtask} 8(30\%)\): No special restrictions.

Sample Explanation 1

There are the following \(8\) possible cases:

• \(a = (1,1,1), b = (1,1,1), ans = 0\)
• \(a = (1,1,2), b = (1,1,2), ans = 0\)
• \(a = (1,2,1), b = (1,1,1), ans = 1\)
• \(a = (1,2,2), b = (1,2,2), ans = 0\)
• \(a = (2,1,1), b = (1,1,1), ans = 1\)
• \(a = (2,1,2), b = (1,1,2), ans = 1\)
• \(a = (2,2,1), b = (2,2,2), ans = 1\)
• \(a = (2,2,2), b = (2,2,2), ans = 0\)

Thus, the answer is \(0 + 0 + 1 + 0 + 1 + 1 + 1 + 0 = 4\).

Note that for a fixed \(a\), the optimal \(b\) is not necessarily unique. The above only provides one possible solution.

Bonus

Achieve \(O(n \log n)\) when \(p\) is an NTT modulus. This part is not difficult based on the main solution of this problem.

见题面 Input 部分

见题面 Output 部分