AT_abc378_e [ABC378E] Mod Sigma Problem

[problemUrl]: https://atcoder.jp/contests/abc378/tasks/abc378_e You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of $N$ non-negative integers, and a positive integer $M$. Find the following value: $$ \sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right). $$ Here, $X \mathbin{\mathrm{mod}} M$ denotes the remainder when the non-negative integer $X$ is divided by $M$.

The input is given from Standard Input in the following format: > $N$ $M$ > > $A_1$ $A_2$ $\dots$ $A_N$

Print the answer.

### 制約 ### Constraints - $1 \leq N \leq 2 \times 10^5$ - $1 \leq M \leq 2 \times 10^5$ - $0 \leq A_i \leq 10^9$ ### Sample Explanation 1 - $A_1 \mathbin{\mathrm{mod}} M = 2$ - $(A_1+A_2) \mathbin{\mathrm{mod}} M = 3$ - $(A_1+A_2+A_3) \mathbin{\mathrm{mod}} M = 3$ - $A_2 \mathbin{\mathrm{mod}} M = 1$ - $(A_2+A_3) \mathbin{\mathrm{mod}} M = 1$ - $A_3 \mathbin{\mathrm{mod}} M = 0$ The answer is the sum of these values, $10$. Note that the outer sum is not taken modulo $M$.