A. Completely Divisible Subarrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of length $$$N$$$. Count the number of subarrays$$$^\dagger$$$ such that the number of elements divisible by $$$K$$$ is divisible by $$$K$$$.

$$$\dagger$$$  A subarray is obtained by deleting several (possibly zero) elements from the start of the array and several (possibly zero) elements from the end of the array.

Input

The first line of the input consists of two space-separated integers $$$N$$$ and $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le K \le 10^9$$$) — the number of elements in the array and the integer $$$K$$$ from the problem statement, respectively.

The second line of the input consists of $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^9$$$).

Output

Output one line containing a single integer — the answer to the problem.

Examples
Input
7 3
1 9 3 4 5 6 6
Output
7
Input
2 1000000000
1 1000000000
Output
1
Note

In the first sample test, the subarrays are:

  • $$$[1]$$$ $$$9$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$6$$$
  • $$$[1$$$ $$$9$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6]$$$ $$$6$$$
  • $$$1$$$ $$$[9$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6]$$$ $$$6$$$
  • $$$1$$$ $$$9$$$ $$$[3$$$ $$$4$$$ $$$5$$$ $$$6$$$ $$$6]$$$
  • $$$1$$$ $$$9$$$ $$$3$$$ $$$[4]$$$ $$$5$$$ $$$6$$$ $$$6$$$
  • $$$1$$$ $$$9$$$ $$$3$$$ $$$[4$$$ $$$5]$$$ $$$6$$$ $$$6$$$
  • $$$1$$$ $$$9$$$ $$$3$$$ $$$4$$$ $$$[5]$$$ $$$6$$$ $$$6$$$

In the second sample test, there's only one subarray: [$$$1$$$] $$$1000000000$$$. This subarray has $$$0$$$ elements divisible by $$$K = 1000000000$$$, and $$$0$$$ is divisible by $$$1000000000$$$.