时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $A$。

将 $A$ 的第 $L$ 位到第 $R$ 位称为子区间 $[L,R]=\{A_L,A_{L+1},\dots,A_R\}$，子区间 $[L,R]$ 的区间和为 $\sum_{i=L}^R A_i=A_L+A_{L+1}+\dots+A_R$。

给定一个正整数 $k$，求 $A$ 有多少个子区间 $[L,R]$ 的区间和是 $k$ 的倍数，即求有多少个子区间 $[L,R]$ 满足 $\sum_{i=L}^R A_i \mod k =0$。

格式

输入格式

第一行包含两个整数 $n,k$，分别表示数组 $A$ 的长度以及求区间和为 $k$ 的倍数的子区间的数量。

第二行包含 $n$ 个整数，表示数组 $A$。

输出格式

输出一个整数表示区间和为 $k$ 的倍数的子区间的数量。

样例

样例输入 #1

6 3
1 2 3 4 5 6

样例输出 #1

11

数据规模

对于 $50\%$ 的数据，$n\leq 5000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^6$，$1\leq k\leq 10^6$，$0\leq A_i \leq 10^9$。