题目描述

怪兽入侵了地球！

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

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

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

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

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

输入格式

第一行两个正整数 $n, k$ 如题所述；

第二行为 $n$ 个正整数，其中第 $i$ 个数 $a_i$ 表示第 $i$ 件武器的攻击力。

输出格式

一行一个整数表示答案。

5 3
1 2 3 4 5

7

样例 $1$ 说明：

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

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

7

6 2
2 2 2 2 2 2

21

数据范围

$20\%$ 的数据：$n,k\le100$；

$40\%$ 的数据：$n,k\le10000,1\le a_i \le k$；

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

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

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