Description

Xiao X has balls of $n$ different colors. For the $i$-th color, there are $a_i$ balls. Balls of the same color are indistinguishable. Define the disorder degree $f(l, r)$ for colors $l \sim r$ as follows: line up all balls of colors $l \sim r$ in a row, and let $f(l, r)$ be the total number of distinct arrangements modulo $p$. Xiao X wants you to help compute the value of:

Input Format

The first line contains two integers $n, p$.

The second line contains $n$ integers $a_i$.

Output Format

Output one integer in one line, representing the answer.

2 2
1 2

3

4 7
1 2 8 9

28

15 5
1 5 26 1 0 5 0 6 7 51 1 5 26 1 0

124

Hint

[Sample 1 Explanation]

This problem uses bundled testdata.

• Subtask 1 (31 points): $1 \le n \le 5 \times 10^5$, $a_i$ is uniformly random in $[0, 10^5]$, time limit $1.5 \text{ s}$.
• Subtask 2 (32 points): $1 \le n \le 5 \times 10^4$, time limit $5 \text{ s}$.
• Subtask 3 (37 points): no special constraints, time limit $2.5 \text{ s}$.

For $100\%$ of the data, $1 \le n \le 5 \times 10^5$, $0 \le a_i \le 10^{18}$, $p \in \{2,3,5,7\}$.

Translated by ChatGPT 5