题目描述

Multiset is a mathematical object similar to a set, but each member of a multiset may have more than one membership.

Just as with any set, the members of a multiset can be ordered in many ways. We call each such ordering a permutation of the multiset. 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 will say that one permutation of a given multiset is smaller (in lexicographic order) than another permutation, if on the first position that does not match the first permutation has a smaller element than the other one. All permutations of a given multiset can be numbered (starting from one) in an increasing order.

Task: Write a programme that reads the description of a permutation of a multiset and a positive integer from the standard input, determines the remainder of the rank of that permutation in the lexicographic ordering modulo $m$, writes out the result to the standard output.

多重集合是数学中的一个概念，它的定义很像集合，但是在多重集之中，同一个元素可以出现多次。

和集合一样，多重集的的元素可以有很多种元素的排布顺序。我们把它叫作多重集的排列。

现在我们定义多重集的某个排列 $s_i$ 比某个排列 $s_j$ 的大小比较为字典序比较。这样某个多重集的排列可以从小到大得排起来。

现在给你一个元素个数为 $n$ 的多重集的一个排列和 $m$，求这个排列的排名取模 $m$。

输入格式

The first line of the standard input holds two integers $n\ (1\le n \le 300000)$ and $m\ (2 \le m \le 10^9)$, separated by a single space. These denote, respectively, the cardinality of the multiset and the number $m$.

The second line of the standard input contains $n$ positive integers $a_i\ (1\le a_i \le 300000)$, separated by single spaces and denoting successive elements of the multiset permutation.

第一行：两个整数 $n,m$。

第二行：$n$ 个数，代表多重集的排列。

输出格式

The first and only line of the standard output is to hold one integer, the remainder modulo $m$ of the rank of the input permutation in the lexicographic ordering.

一行一个整数 排名取模 $m$。

4 1000
2 1 10 2

5

提示

感谢@远航之曲 贡献的翻译。