가장 긴 증가하는 부분수열의 개수

수열 $A$의 가장 긴 강한 증가 부분수열(strictly increasing subsequence)의 개수를 $m$으로 나눈 나머지를 구하세요.

부분수열이란 $A$에서 $0$개 이상의 원소를 지우고 남은 원소들의 상대적 순서를 유지한 수열입니다. 강한 증가 부분수열은 바로 앞 원소보다 항상 더 큰(같으면 안 되고 반드시 더 큰) 원소가 이어지는 부분수열을 뜻합니다. 이러한 강한 증가 부분수열 중 길이가 가장 긴 것을 세는데, 그런 부분수열은 여러 개일 수 있으므로 그 개수를 구하면 됩니다. 두 부분수열은 선택한 원소의 위치 집합이 다르면 서로 다른 것으로 봅니다.

첫째 줄에 수열 $A$의 길이 $n$과 나눌 수 $m$이 주어집니다 ($1 \le n \le 500\,000$, $1 \le m \le 10^9$).

둘째 줄에 $A$의 원소 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어집니다 ($0 \le a_i \le 10^9$).

가장 긴 강한 증가 부분수열의 개수를 $m$으로 나눈 나머지를 한 줄에 출력하세요.