Background

Special for beginners, ^_^

Description

定义一个序列是完美序列如果该序列长度等于序列内所有元素的和对 $k$ 取模。

给定一个序列和一个 $k$，求子序列中的完美序列数量。

Format

Input

第一行两个正整数 $n(\le2\times10^5)$ 和 $k(\le10^9)$ ，分别表示区间长度和模数。

第二行按顺序给出 $n$ 个不超过 $10^9$ 的正整数，表示从左到右序列中的每一个数。

Output

完美子区间的数量。

Samples

5 4
1 1 4 5 1 4

6

Limitation

1s, 1024KiB for each test case.