题目描述

给你一个长度为 $n$ 的非负整数数组 $a_1,a_2,...,a_n$，再给你一个正整数 $k$，问你有多少个区间 $[l,r]$ 满足 $a_l+a_{l+1}+...+a_r$ 是 $k$ 的倍数。

输入格式

第一行两个整数 $n,k$。
第二行 $n$ 个整数，表示 $a_1,a_2,...,a_n$。

输出格式

一行一个整数，表示答案。

输入输出样例 #1

输入 #1

5 3
3 6 1 4 5

输出 #1

4

说明/提示

$1\le n,k\le 10^6,0\le a_i\le 10^9$。