【题目描述】

怪兽入侵了地球！
为了抵抗入侵，人类设计出了按顺序排列好的 $n$ 件武器，其中第 $i$ 件武器的攻击力为 $a_i$，可以造成 $a_i$ 的伤害。

武器已经排好了，因此不能改变顺序。某件武器可以单独攻击，也可以与相邻的武器进行组合攻击。具体来说，每次可以选择第一个（可以为 1 个，即不进行组合）连续的武器组合来进行攻击，则攻击力为这些连续的武器攻击力之和。

来自外星的怪兽拥有无敌伤害，不会受到任何伤害。

但是人类在交战过程中发现怪兽有致命的弱点：每次会受到 $k$ 或 $k$ 的倍数的伤害时，怪兽的无敌护盾就被打破了。

请帮忙人类设计有多少种组合武器的方案，使得造成的伤害能打破怪兽的无敌护盾。

【输入格式】

第一行两个正整数 $n, k$ 如所描述；
第二行有 $n$ 个正整数，其中第$i$个数$a_i$ 表示第 $i$ 件武器的攻击力。

【输出格式】

一行一个整数表示答案。

【样例 1 输入】

5 3  
1 2 3 4 5  

【样例 1 输出】

7  

【样例 2 输入】

10 11 
1 4 8 10 16 19 21 25 30 43  

【样例 2 输出】

7  

【样例 3 输入】

6 2  
2 2 2 2 2 2  

【样例 3 输出】

21  

【样例解析】

样例 1 解释：

$k=3$，而区间 $[1, 2]、[1, 3]、[1, 5]、[2, 4]、[3, 3]、[3, 5]、[4, 5]$ 的区间和均为 $3$ 或 $3$ 的倍数，故一共有 $7$ 种方案。

【数据范围】

$20\%$ 的数据，$n, k ≤ 100$;

$40\%$ 的数据，$n, k ≤ 10000, 1 ≤ a_i ≤ k$;

另外存在 $10\%$的数据，$k = 2$。

另外存在$10\%$的数据，所有的$a_i$均相等。

$100\%$的数据，$1≤ n≤ 10^6,2≤ k≤ 10^6,1≤ a_i≤ 10^9$。