[POI2008]Per

时间限制:10s      空间限制:162MB

题目描述

给你一个序列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


题目来源

没有写明来源