题目描述

题目译自 XV OI Olimpiada Informatyczna – III etap Permutacja

多重集是一个类似于集合的数学对象，但其中相同的元素可以出现多次。与集合类似，多重集的所有元素可以排列成一个序列，而且通常有多种排列方式；每种排列方式称为多重集的一个排列。例如，多重集 $\{1,1,2,3,3,3,7,8\}$ 的排列包括 $(2,3,1,3,3,7,1,8)$ 和 $(8,7,3,3,3,2,1,1)$ 等。

我们说给定多重集的一个排列在字典序中小于另一个排列，如果在两者首次不同的位置上，第一个排列的元素小于第二个排列的元素。可以按照从最小到最大的字典序对多重集的所有排列进行编号（从 $1$ 开始）。

编写一个程序，完成以下功能：

• 从标准输入读取某个多重集的排列描述以及一个正整数 $m$，
• 计算该排列在字典序中的编号，具体来说是该编号除以 $m$ 的余数，
• 将结果输出到标准输出。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 300000, 2 \leq m \leq 10^9)$，用单个空格分隔，分别表示多重集中的元素数量和数字 $m$。

第二行包含 $n$ 个正整数 $a_{i}$ $(1 \leq a_{i} \leq 300000)$，用单个空格分隔，表示给定多重集排列的各个元素。

输出格式

输出应包含一行，且仅一行，包含一个整数，表示给定排列在字典序中的编号除以 $m$ 的余数。

4 1000
2 1 10 2

5

所有在字典序中小于给定排列的排列依次为：$(1,2,2,10)$、$(1,2,10,2)$、$(1,10,2,2)$ 和 $(2,1,2,10)$。