Description

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

Input

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

Output

排名mod m

Samples

4 1000
2 1 10 2

5

Limitation

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