题目描述

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 integerm 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 \dots\ 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

提示

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