[POI2008]Per

给定一个序列 $s$。将该序列的所有不同排列按字典序从小到大排列，求序列 $s$ 的排名对 $m$ 取模后的结果。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示序列长度和模数。

第二行包含 $n$ 个整数 $S_1,S_2,\ldots,S_n$，表示序列 $s$。

输出格式

输出一个整数，表示序列 $s$ 的排名对 $m$ 取模后的结果。

样例输入

4 1000
2 1 10 2

样例输出

5

数据范围

• $1\le n\le 3\times 10^5$；
• $2\le m\le 10^9$；
• $1\le S_i\le 3\times 10^5$。

来源与许可

本题为 POI 2008 试题「Per」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 1000
2 1 10 2

输出

5