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