### 问题描述 一个整数序列 $A=\left(a_1, a_2, \cdots, a_n\right)$ 的区间和为 $S_{i, j}=a_i+a_{i+1}+\cdots+a_j$ 。 给定整数序列 $A$ 和一个正整数 $k$, 请问有多少个区间 $[i, j]$ 满足 $1 \leq i \leq j \leq n$ 且 $S_{i, j}$ 是 $k$ 非负整数倍。 ### 输入格式 输入的第一行包含两个整数 $n 、 k$, 用一个空格分隔。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$, 相邻的整数之间用一个空格分隔。 ### 输出格式 输出一行包含一个数表示满足条件的区间数量。 ### 样例输入 ```text 7 3 1 -1 0 2 2 2 -30 ``` ### 样例输出 ```text 7 ``` ### 样例说明 满足条件的区间有 $[1,2],[1,3],[1,6],[2,5],[3,3],[3,6],[4,6]$ 。 ### 评测用例规模与约定 对于 $40 \%$ 的评测用例, $1 \leq n \leq 500,1 \leq k \leq 10$; 对于 $60 \%$ 的评测用例, $1 \leq n \leq 2000$; 对于所有评测用例, $1 \leq n \leq 100000,1 \leq k \leq 10^9,-10^9 \leq a_i \leq 10^9$ 。