多重集（multiset）是一种类似于集合的数学对象，但多重集中的每个成员可以出现多次。与任何集合一样，多重集的成员可以以多种方式排序。我们将每种这样的排序称为该多重集的一个排列。例如，多重集 $\{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 \le n \le 300\,000$，$2 \le m \le 1\,000\,000\,000$），中间用单个空格分隔。它们分别表示多重集的基数和模数 $m$。标准输入的第二行包含 $n$ 个正整数 $a_i$（$1 \le a_i \le 300\,000$），用单个空格分隔，表示多重集排列的连续元素。

输出格式

标准输出的第一行且仅包含一行，输出输入排列在字典序中的排名对 $m$ 取模后的余数。

样例

输入 1

4 1000
2 1 10 2

输出 1

5

说明 1

所有小于（按字典序）给定排列的排列为：$(1,2,2,10)$，$(1,2,10,2)$，$(1,10,2,2)$ 和 $(2,1,2,10)$。