You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

B. 区间计数

题目描述

给定一个长度为 $n$ 的数列 $\{a_i\}$，求满足区间和为 $k$ 的倍数的非空子区间数。

输入格式

输入第一行为两个正整数 $n\ k$ 第二行 $n$ 个正整数，表示数列 $\{a_i\}$

输出格式

输出答案

样例

样例一

输入

3 2
2 4 6

输出

6

样例二

输入

5 2
2 4 5 8 10

输出

6

数据范围与提示

• 对于 $50\%$ 的数据：$1 \le n \le 1000, 1 \le k \le 1000$
• 对于 $80\%$ 的数据：$1 \le n \le 200000, 1 \le k \le 1000$
• 对于 $100\%$ 的数据：$1 \le n \le 200000, 1 \le k \le 1000000000, 1 \le a_i \le 1000000000$