题目描述

一个整数序列 $A=(a_1,a_2,⋯ ,a_n)$ 的区间和为 $S_{i,j}=a_i+a_{i+1}+⋯+a_j$ 。

给定整数序列 $A$ 和一个正整数 $k$ , 请问有多少个区间 $[i,j]$ 满足 $1≤i≤j≤n$ 且 $S_{i,j}$ 是 $k$ 非负整数倍。

输入描述

输入的第一行包含两个整数 $n,k$ , 用一个空格分隔。

第二行包含 $n$ 个整数 $a_1,a_2,⋯ ,a_n$ , 相邻的整数之间用一个空格分隔。

输出一行包含一个数表示满足条件的区间数量。

7 3
1 -1 0 2 2 2 -30

满足条件的区间有 $[1,2],[1,3],[1,6],[2,5],[3,3],[3,6],[4,6]$ 。

对于 40% 的评测用例, $1≤n≤500,1≤k≤10$ ;

对于 60% 的评测用例, $1≤n≤2000$ ;

对于所有评测用例, $1≤n≤100000，1≤k≤10^9，−10^9≤a_i≤10^9$ 。