Multiset Permutation Rank

A multiset is like a set, except each value may appear more than once. As with a set, the members of a multiset can be arranged in many orders, and each such arrangement is called a permutation of the multiset. For example, two permutations of the multiset $\{1, 1, 2, 3, 3, 3, 7, 8\}$ are $(2, 3, 1, 3, 3, 7, 1, 8)$ and $(8, 7, 3, 3, 3, 2, 1, 1)$.

Permutations are compared in lexicographic order: one permutation is smaller than another if, at the first position where they differ, its element is smaller. If we list all distinct permutations of a given multiset in increasing lexicographic order and number them starting from $1$, the number assigned to a permutation is its rank.

You are given one permutation of a multiset and a positive integer $m$. Compute the rank of that permutation and output the rank modulo $m$.

The first line contains two integers $n$ and $m$ ($1 \le n \le 300{,}000$, $2 \le m \le 1{,}000{,}000{,}000$): the number of elements in the multiset and the modulus $m$.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 300{,}000$), separated by single spaces, giving the elements of the multiset permutation in order.

Print a single integer: the rank of the given permutation in lexicographic order, taken modulo $m$.

Consider the permutation $(2, 1, 10, 2)$ of the multiset $\{1, 2, 2, 10\}$. The permutations that are smaller than it in lexicographic order are $(1, 2, 2, 10)$, $(1, 2, 10, 2)$, $(1, 10, 2, 2)$, and $(2, 1, 2, 10)$. There are four of them, so the rank of $(2, 1, 10, 2)$ is $5$, and $5 \bmod 1000 = 5$.