题目描述

在 Russland 的小学留学强哥每天除了学算法，还会绕学校旁边的湖跑步。这个学校每学期都会有一个跑步指标，总的里程必须不小于 $20$ 公里，否则体育成绩就会被判作不及格。

湖旁边有环湖跑道，跑道上有 $n$ 个检测点，编号分别是 $1\sim n$。强哥跑步的时候只能从某个检测点出发，然后在某个检测点停下来。

为了方便计算每天消耗的热量，强哥希望他的跑步距离是 $m$ 的倍数（单位：米）。

现在给了你每个检测点到下一个检测点之间的距离，现在问强哥有多少种选择起点和终点的方案。

注意：由于强哥的耐力还不够强，所以他的跑步总里程总是会 小于 环湖跑道的周长。

输入格式

第一行有两个数 $n,m$。

第二行为 $n$ 个数，其中第 $i$ 个数 $a_i$ 表示第 $i$ 个检测点到下一个检测点之间的距离。需要说明的是，第 $n$ 个检测点的下一个点是第 $1$ 个检测点。

输出格式

输出答案作为一个整数。

4 3
2 1 4 3

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$