该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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.