#1129. [POI2008]Per

题目描述

给你一个序列s，你把这个序列的所有不同排列按字典序排列后，求s的排名mod m

输入格式

序列的长度n<300 000,m n个数，代表序列s

输出格式

排名mod m

样例

样例输入

4 1000  

2 1 10 2

样例输出

5

数据范围与提示

All the permutations smaller (with respect to lexicographic order) than the one given are: (1,2,2,10), (1,2,10,2), (1,10,2,2) and (2,1,2,10). 2<=m<=10^9,1<=Si<=300000