Mimi is helping out at a daycare! There are $M$ children and $N$ boxes of crayons in a row, the $i^{\text{th}}$ of which has $c_i$ crayons. Mimi will choose a single contiguous section of crayon boxes to give to the children. In order to be fair, she also wants the total number of crayons in the subarray she chooses to be divisible by $M$ so that it can be split equally. How many ways can she do this?

Constraints

For all subtasks:

$1\le c_i\le {10}^9$

Subtask 1 [20%]

$1\le N\le 100$
$1\le M\le {10}^9$

Subtask 2 [20%]

$1\le N\le 2000$
$1\le M\le {10}^6$

Subtask 3 [40%]

$1\le N\le {10}^5$
$1\le M\le {10}^6$

Subtask 4 [20%]

$1\le N\le {10}^5$
$1\le M\le {10}^9$

Input Specification

The first line will have two space separated integers, $N$ and $M$.
The second line will have $N$ space separated integers, $c_1,c_2,\dots ,c_N$.

Output Specification

A single integer, the number of subarrays which have a total which is a multiple of $M$. This number may overflow 32-bit integers.

Sample Input

5 6
3 5 9 6 10

Sample Output

2

Explanation for Sample

The two subarrays with a sum divisible by 6 are $[6]$ and $[5,9,6,10]$.