다중집합 순열의 순위

다중집합은 집합과 비슷하지만 각 원소가 두 번 이상 나타날 수 있습니다. 집합처럼 다중집합의 원소들도 여러 순서로 나열할 수 있으며, 그렇게 나열한 것 하나하나를 그 다중집합의 순열이라고 부릅니다. 예를 들어 다중집합 $\{1, 1, 2, 3, 3, 3, 7, 8\}$의 순열로는 $(2, 3, 1, 3, 3, 7, 1, 8)$과 $(8, 7, 3, 3, 3, 2, 1, 1)$ 등이 있습니다.

순열은 사전식 순서로 비교합니다. 두 순열을 앞에서부터 비교했을 때 처음으로 달라지는 위치에서 더 작은 원소를 가진 쪽이 더 작은 순열입니다. 주어진 다중집합의 서로 다른 순열을 모두 사전식 오름차순으로 정렬하고 $1$부터 번호를 매겼을 때, 어떤 순열에 매겨진 번호를 그 순열의 순위라고 합니다.

다중집합의 순열 하나와 양의 정수 $m$이 주어집니다. 이 순열의 순위를 구하고, 그 값을 $m$으로 나눈 나머지를 출력하세요.

첫째 줄에 두 정수 $n$과 $m$이 주어집니다 ($1 \le n \le 300{,}000$, $2 \le m \le 1{,}000{,}000{,}000$). 각각 다중집합의 원소 개수와, 나머지를 취하는 수 $m$입니다.

둘째 줄에 다중집합 순열의 원소를 순서대로 나타내는 $n$개의 양의 정수 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어집니다 ($1 \le a_i \le 300{,}000$).

주어진 순열의 사전식 순위를 $m$으로 나눈 나머지를 정수 하나로 출력합니다.

다중집합 $\{1, 2, 2, 10\}$의 순열 $(2, 1, 10, 2)$를 생각해 봅시다. 사전식 순서에서 이 순열보다 작은 순열은 $(1, 2, 2, 10)$, $(1, 2, 10, 2)$, $(1, 10, 2, 2)$, $(2, 1, 2, 10)$의 네 개입니다. 따라서 $(2, 1, 10, 2)$의 순위는 $5$이고, $5 \bmod 1000 = 5$입니다.