Lexicographic Rank of a Multiset Permutation

A multiset is a generalization of a set that allows multiple instances of its elements. Consider a multiset with n elements and a permutation of those elements. The lexicographic rank of a permutation is defined by ordering all the distinct permutations of the multiset in increasing lexicographic order (i.e. dictionary order) and then numbering them starting from 1. In this problem the lexicographic order is defined as follows:

Given two permutations \(s_i\) and \(s_j\) of the same multiset, \(s_i < s_j\) if at the first position where they differ, the element in \(s_i\) is smaller than the element in \(s_j\).

Your task is to compute the rank of a given permutation in this order, and then output the remainder when this rank is divided by a given positive integer m. The rank is computed exactly using the formula

[ \text{rank} = 1 + \sum_{i=1}^{n} \left( \text{number of valid permutations with a smaller element at position } i \right) ]

where the number of valid permutations for a given configuration is computed by

[ \frac{(n-i)!}{\prod_{x} (f_x)!}]

with (f_x) being the frequency of element (x) remaining in the multiset.

Note: The final answer is the computed rank modulo m.

inputFormat

The input is read from standard input. The first line contains two integers n and m where n is the number of elements in the permutation and m is the modulus value. The second line contains n integers representing the permutation of the multiset. It is guaranteed that the input permutation comes from a multiset (i.e. duplicate elements may appear).

outputFormat

Output a single integer: the lexicographic rank of the given permutation modulo m.

sample

8 1000
2 3 1 3 3 7 1 8

981