题目描述

给定一个数列 a1,a2,…,an，若有一个区间 [L,R] 满足

a_l+a_l+1+...+a_r−1+a_r

为 k 的倍数，则称[L,R] 为k的倍数区间 。

给定k，请统计在给定的数列中，有多少个区间是 k 的倍数区间。

输入格式

第一行：两个整数 n 与 k；
第二行：n 个整数 a1,…,an。

输出格式

单个整数：表示倍数区间的数量。

数据范围

对于 30% 的数据，n≤200；

对于 60% 的数据，n≤5000；

对于 100% 的数据，1≤n≤200000；

1≤k≤100000，0≤ai≤10000。

样例数据

输入:

4 20

30 20 40 10

输出:

4

说明:

满足要求的区间有：[20],[40],[20,40],[30,20,40,10]