Number of Longest Increasing Subsequences

Compute the number of longest strictly increasing subsequences of a sequence $A$, modulo $m$.

A subsequence is obtained from $A$ by deleting zero or more elements while keeping the relative order of the remaining ones. A strictly increasing subsequence is one in which every element is strictly greater than the element before it. Among all strictly increasing subsequences, the longest ones are those of maximum length; there may be several of them, and you must count how many there are. Two subsequences are considered different when they use different sets of positions of $A$.

The first line contains the length $n$ of the sequence $A$ and the modulus $m$ ($1 \le n \le 500\,000$, $1 \le m \le 10^9$).

The second line contains the elements $a_1, a_2, \dots, a_n$ of $A$, separated by spaces ($0 \le a_i \le 10^9$).

Print a single line containing the number of longest strictly increasing subsequences of $A$, taken modulo $m$.