怪兽入侵了地球！
为了抵抗入侵，人类设计出了按顺序排列好的 n 件武器，其中第 i 件武器的攻击力为 ai，可以造成 ai 的伤害。
武器已经排列好了，因此不能改变顺序。某件武器可以单独攻击，也可以与相邻的武器 进行组合攻击。具体来说，每次你可以把相邻的若干个（可以为 1 个，即不进行组合）连续 的武器组合起来进行攻击，则攻击力为这些连续的武器攻击力之和。
来自外星的怪兽拥有无敌护盾，不会受到任何伤害。
但是人类在交战过程中发现怪兽有个致命的弱点：每次当受到 k 或 k 的倍数的伤害 时，怪兽的无敌护盾就能被打破。
请你帮助人类求出有多少种组合武器的方案，使得造成的伤害能打破怪兽的无敌护盾。
第一行两个正整数 n, k 如题所述；
第二行为 n 个正整数，其中第 i 个数 ai 表示第 i 件武器的攻击力。
样例1
5 3
1 2 3 4 5
样例2
10 11
1 4 8 10 16 19 21 25 30 43
样例3
6 2
2 2 2 2 2 2
样例1
7
样例2
7
样例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 ≤ ai ≤ k；
另外存在10% 的数据，k = 2；
另外存在10% 的数据，所有的 ai 均相等。
100% 的数据，1 ≤ n ≤ 10^6 , 2 ≤ k ≤ 10^6
, 1 ≤ ai ≤ 10^9