计步器

题目描述

湖边有 $N$ 个休息区。

休息区按顺时针方向编号为 $1$, $2$, ..., $N$。

从休息区 $i$ 顺时针走到休息区 $i+1$（其中休息区 $N+1$ 指休息区 $1$）需要走 $A_i$ 步。

从休息区 $s$ 顺时针走到休息区 $t$（$s \neq t$）所需的最少步数是 $M$ 的倍数。

求满足条件的数对 $(s,t)$ 的个数。

输入格式

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

$N$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案，为一个整数。

样例

4 3
2 1 4 3

4

从休息区 $1$ 顺时针走到休息区 $2$ 所需的最少步数是 $2$，不是 $3$ 的倍数。

从休息区 $1$ 顺时针走到休息区 $3$ 所需的最少步数是 $3$，是 $3$ 的倍数。

从休息区 $1$ 顺时针走到休息区 $4$ 所需的最少步数是 $7$，不是 $3$ 的倍数。

从休息区 $2$ 顺时针走到休息区 $3$ 所需的最少步数是 $1$，不是 $3$ 的倍数。

从休息区 $2$ 顺时针走到休息区 $4$ 所需的最少步数是 $5$，不是 $3$ 的倍数。

从休息区 $2$ 顺时针走到休息区 $1$ 所需的最少步数是 $8$，不是 $3$ 的倍数。

从休息区 $3$ 顺时针走到休息区 $4$ 所需的最少步数是 $4$，不是 $3$ 的倍数。

从休息区 $3$ 顺时针走到休息区 $1$ 所需的最少步数是 $7$，不是 $3$ 的倍数。

从休息区 $3$ 顺时针走到休息区 $2$ 所需的最少步数是 $9$，是 $3$ 的倍数。

从休息区 $4$ 顺时针走到休息区 $1$ 所需的最少步数是 $3$，是 $3$ 的倍数。

从休息区 $4$ 顺时针走到休息区 $2$ 所需的最少步数是 $5$，不是 $3$ 的倍数。

从休息区 $4$ 顺时针走到休息区 $3$ 所需的最少步数是 $6$，是 $3$ 的倍数。

因此，满足条件的数对 $(s,t)$ 共有 4 对。

2 1000000
1 1

0

9 5
9 9 8 2 4 4 3 5 3

11

数据范围

• 所有输入值均为整数。
• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^9$
• $1 \le M \le 10^6$