当前没有测试数据。

Background

怪兽入侵了地球！

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

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

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

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

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

Format

Input

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

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

Output

一行一个整数表示答案。

Samples

5 3
1 2 3 4 5

7

Limitation

对于 20% 的数据，满足 1≤n,k≤100。

对于 40% 的数据，满足 1≤n,k≤10$^4$,1≤a$_i$≤k。

对于另外 10% 的数据，满足 k=2。

对于另外 10% 的数据，满足所有的 a$_i$均相等。

对于 100% 的数据，满足 1≤n≤10$^6$,2≤k≤10$^6$,1≤a$_i$≤10$^9$。