Problem Description

A multiset is like a set, but elements may appear more than once.

A permutation of a multiset is any ordering of its elements. For example, among the permutations of the multiset $\{1, 1, 2, 3, 3, 3, 7, 8\}$, there are $\{2, 3, 1, 3, 3, 7, 1, 8\}$ and $\{8, 7, 3, 3, 3, 2, 1, 1\}$.

We use lexicographic order to compare two permutations: at the first position where they differ, the permutation with the smaller element is considered smaller. All permutations of a given multiset can be sorted increasingly and numbered starting from $1$ (this number is called the rank).

Task: Given a permutation of a multiset of size $n$ and a positive integer $m$, compute the remainder modulo $m$ of the rank of this permutation in lexicographic order.

Input Format

• The first line contains two integers $n$ and $m$ ($1 \le n \le 300000,\ 2 \le m \le 10^9$): the size of the multiset and the modulus $m$.
• The second line contains $n$ positive integers $a_i$ ($1 \le a_i \le 300000$), the given permutation of the multiset.

Output Format

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

4 1000
2 1 10 2

5

Hint

Thanks to @远航之曲 for the translation.

Translated by ChatGPT 5.