问题陈述

给定一个由 $N$ 个非负整数组成的序列 $A = (A_1, A_2, \dots, A_N)$ 和一个正整数 $M$。

求以下值：

$$\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right).$$

这里，$X \mathbin{\mathrm{mod}} M$ 表示非负整数 $X$ 除以 $M$ 的余数。

约束

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$

输入

输入从标准输入按以下格式给出：

$N M$ $A_1 A_2 \dots A_N$

输出

输出答案。

样例输入 1

3 4
2 5 0

样例输出 1

10

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

这些值的和为 $10$。注意，外层的求和不对 $M$ 取模。

样例输入 2

10 100
320 578 244 604 145 839 156 857 556 400

样例输出 2

2736