U501260 消灭怪兽 (monster)

怪兽入侵了地球！\ 为了抵抗入侵，人类设计出了按顺序排列好的 $n$ 件武器，其中第 $i$ 件武器的攻击力为 $a_i$，可以造成 $a_i$ 的伤害。\ 武器已经排列好了，因此不能改变顺序。某件武器可以单独攻击，也可以与相邻的武器进行组合攻击。具体来说，每次你可以把相邻的若干个（可以为 1 个，即不进行组合）连续的武器组合起来进行攻击，则攻击力为这些连续的武器攻击力之和。\ 来自外星的怪兽拥有无敌护盾，不会受到任何伤害。\ 但是人类在交战过程中发现怪兽有个致命的弱点：每次当受到 $k$ 或 $k$ 的倍数的伤害时，怪兽的无敌护盾就能被打破。\ 请你帮助人类求出有多少种组合武器的方案，使得造成的伤害能打破怪兽的无敌护盾。

输入文件为 `monster.in`。 第一行两个正整数 $n$，$k$，如题所述； 第二行为 $n$ 个正整数，其中第 $i$ 个数 $a_i$ 表示第 $i$ 件武器的攻击力。

输出文件为 `monster.out`，一行一个整数表示答案。

**样例说明**\ 样例 1 解释： k=3，而区间 `[1, 2]`, `[1, 3]`, `[1, 5]`, `[2, 4]`, `[3, 3]`, `[3, 5]`, `[4, 5]` 的区间和均为 3 或 3 的倍数，故一共有 7 种方案。 --- 20% 的数据，$n, k \leq 100$；\ 40% 的数据，$n, k \leq 10^4$, $1 \leq a_i \leq k$；\ 另外存在 10% 的数据，$k = 2$；\ 另外存在 10% 的数据，所有的 $a_i$ 均相等；\ 100% 的数据，$1 \leq n \leq 10^6$, $2 \leq k \leq 10^6$, $1 \leq a_i \leq 10^9$。