Summation of Isotonic Regression Costs

You are given three integers n, m, and a prime p. Consider an integer sequence a of length n where each element satisfies \(1 \le a_i \le m\). For each such sequence, define its isotonic regression cost as follows.

Let \(a = [a_1,a_2,\dots,a_n]\). We wish to select a monotone non-decreasing real sequence \(b = [b_1,b_2,\dots,b_n]\) that minimizes \[ \sum_{i=1}^{n} |a_i - b_i|. \] It can be proved that the minimum value is always an integer. In other words, if we denote \[ f(a) = \min_{b_1 \le b_2 \le \dots \le b_n,\, b_i \in \mathbb{R}} \sum_{i=1}^{n} |a_i-b_i|, \] then \(f(a)\) is an integer.

Your task is to compute the sum \[ S = \sum_{a \in [1,m]^n} f(a) \mod p, \] where the summation is taken over all \(m^n\) possible sequences \(a\). Note that even though the optimal \(b\) is chosen from \(\mathbb{R}^n\), the optimum cost is always an integer.

Hint: The classic isotonic regression problem (with the \(\ell_1\) loss) can be solved using the Pool Adjacent Violators Algorithm (PAVA). For a constant segment, the optimal constant is the median of the segment, and the cost is \(\sum |a_i-\text{median}|\). You may simulate this merging process on small \(n\) by maintaining segments and merging them when the monotonicity is violated.

inputFormat

The first and only line of input contains three space-separated integers: n (the length of the sequence), m (the maximum value of each element), and p (a prime number for modulo operations).

\(1 \le n, m \le \text{small}\) (the data ranges are set such that a brute force solution is feasible).

outputFormat

Output a single integer, the value of \(S = \sum_{a \in [1,m]^n} f(a)\) taken modulo p.

sample

1 3 7

0