Little X has $n$ types of balls, where there are $a_i$ balls of the $i$-th color, and balls of the same color are indistinguishable. The chaos degree $f(l, r)$ of colors $l$ through $r$ is defined as the number of ways to arrange all balls of colors $l$ through $r$ in a row, modulo $p$. Little 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

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

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

Output

Output a single integer representing the answer.

Examples

Input 1

2 2
1 2

Output 1

3

Note 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$$

Input 2

4 7
1 2 8 9

Output 2

28

Input 3

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

Output 3

124

Subtasks

This problem uses bundled testing.

• Subtask 1 (31 points): $1 \le n \le 5 \times 10^5$, $a_i$ are 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 restrictions, 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\}$.