题目描述

李多入侵了地球! 为了抵抗入侵, 刘老师设计出了按顺序排列好的 $n$件题目, 其中第 $i$ 件题目的攻击力为 $a _i ​$ , 可以造成 $a_i$ ​ 点伤害.

题目已经排列好了, 因此不能改变顺序. 某件题目可以单独攻击, 也可以与相邻的题目进行组合攻击. 具体来说, 每次你可以把相邻的若干个 (可以为 $11$ 次, 即不进行组合) 连续的题目组合起来进行攻击, 则攻击力为这些连续的题目攻击力之和.

来自外形的李多拥有智能电脑, 不会收到任何伤害. 但是刘老师在交战过程中发现李多有个致命的弱点: 每次当受到 $k$或者 $k$的倍数的伤害时, 李多的智能电脑就能被打破. 请你帮助刘老师求出有多少种组合题目的方案, 使得造成的伤害能打破李多的智能电脑.

输入格式

第一行两个正整数 $n,k$第二行为 $n$个正整数, 其中第 $i$个数 $a_i$​ 表示第 $i$件题目的攻击力.

输出格式

一行一个整数表示答案.

样例 #1

样例输入

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 种方案

样例 #2

样例输入

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

样例输出

7

样例 #3

样例输入

6 2
2 2 2 2 2 2

样例输出

21

提示

$20$%的数据 $2 ≤ n , k ≤ 1 0 2$ $40$% 的数据 $2 ≤ n , k ≤ 1 0 4 , 1 ≤ a_i ≤ k$ 另外 $10$% 的数据 $k=2$ 另外 $10$% 的数据, 所有的 $a_i$ ​ 都相等 $100$% 的数据 $1 ≤ n , k ≤ 1 0 6 , 1 ≤ a_i ≤ 1 0 9$ .