Are you sad ? Don't be, unlike me

You are given a sad array $A$ of size $N$ and an additional sad integer $K$. Now, we create a new sad array $B$, of size $N \cdot K$, where $B[i] = A[i]$, for $0 \le i \le N-1$ and $B[i]=B[i-N]$ for $N \le i \le (N \cdot K) -1$.

Now, we define an inversion to be a pair of indices $(E1,E2)$ lying in the same subsequence $S$, such that $E1 < E2$, but $B[E1] > B[E2]$

Now, you need to cut this sad array $B$ into any number of sad non-empty non-intersecting subsequences. Each element from the given array should belong to exactly one of the subsequences. Let the array be cut into the set of subsequences $\{ S_0, S_1, ...S_{k-1} \}$. Let $Z$ be the sum of the number of inversions in each individual subsequence.

You know what's next right? Considering the array can be cut into each distinct set of subsequences with equal probability, you need to find the Expected Value of $Z$. What this means is that let the array be cut into the set of subsequences $\{ S_0,S_1..S_{k-1} \}$ or into subsequences $\{ C_0,C_1..C_{l-1} \}$, where $S \ne C$. The probability of array being in state $S$ or in state $C$ is equal to the probability of the array being cut into any other set of subsequences.

Let the answer be an irreducible fraction $P / Q$. You need to print $P \cdot Q^{-1}$ Modulo a given prime number $M$. It is guaranteed, that for all of the given tests, $Q \not\equiv 0$ Modulo $M$. So, the answer will always exist and is unique for the given test-set, since $M$ is prime.

Input Format:

The first line contains $3$ space separated integers $N$, $K$ and $M$. The next line contains $N$ space-separated integers, where the $i^{th}$ integer denotes $A[i]$.

Output Format:

Print the given answer on a single line

Constraints :

$1 \le N \le 2000$

$1 \le A[i] \le 10^9$

$1 \le K \le 10^{10}$

$3 \le M \le 5 \cdot 10^4$

$M$ is a prime number