Problem Description

Xiao X has \( n \) types of balls, where the \( i \)-th type has \( a_i \) balls, and balls of the same color are indistinguishable. Define the chaos degree \( f(l, r) \) for the \( l \)-th to \( r \)-th types of balls as the total number of ways to arrange all balls of these types in a row, modulo \( p \). Xiao X would like you to help calculate the value of the following expression:

\[ \sum_{l=1}^n \sum_{r=l}^n f(l, r) \]

Input Format

The first line contains two integers \( n \) and \( p \).

The second line contains \( n \) integers \( a_i \).

Output Format

Output a single integer, which is the answer.

Sample Input and Output

Sample Input #1

2 2
1 2

Sample Output #1

3

Sample Input #2

4 7
1 2 8 9

Sample Output #2

28

Sample Input #3

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

Sample Output #3

124

Notes

Explanation of Sample 1:

\[ f(1,1) = 1 \bmod 2 = 1 \]

\[ f(1,2) = 3 \bmod 2 = 1 \]

\[ f(2,2) = 1 \bmod 2 = 1 \]

\[ \sum_{l=1}^n \sum_{r=l}^n f(l, r) = 3 \]

This problem uses batched testing.

• Subtask 1 (31 points): \( 1 \le n \le 5 \times 10^5 \), \( a_i \) is uniformly random in the range \([0, 10^5]\), time limit is 1.5 seconds.
• Subtask 2 (32 points): \( 1 \le n \le 5 \times 10^4 \), time limit is 5 seconds.
• Subtask 3 (37 points): No special restrictions, time limit is 2.5 seconds.

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\} \).

见题面 Input 部分

见题面 Output 部分