题目描述

给定一个长度为 $n$ 的正整数数组，以及一个正整数 $K$。

如果一个非空连续区间内所有元素的和是 $K$ 的倍数，就称它为一个 K 倍区间。请统计 K 倍区间的数量。

两个区间只要左端点或右端点不同，就分别计数。

输入格式

第一行两个整数 $n,K$。

第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示 K 倍区间的数量。

5 3
1 2 3 4 5

7

3 1
1000000000 1000000000 1000000000

6

样例 1 解释

七个区间分别为 $[1,2]$、$[1,3]$、$[1,5]$、$[2,4]$、$[3,3]$、$[3,5]$、$[4,5]$。

样例 2 解释

任意整数都是 $1$ 的倍数，长度为 $3$ 的数组共有 $6$ 个非空连续区间。

数据范围与提示

对于所有测试点：$1\le n,K\le 200000$，$1\le a_i\le 10^9$。

共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。以下限制均在完整数据范围的基础上额外成立；未列出的参数仍遵守完整数据范围。

测试点编号	额外规模限制
1—5	$n,K\le30$
6—10	$n,K\le2000$
11—20	无额外限制

时间限制：2 秒。内存限制：128 MiB。