You are given an integers array $A$ of $n$ elements. Count the number of subarray with sum divisible by $d$.
A subarray is a contiguous sequence of elements within an array. For example, given an array $B = [1, 2, 3, 4, 5]$, array C = $[2, 3, 4]$ is a subarray of $B$.
### Input
- The first line contains 2 integers $n, d$.
- The second line contains $n$ integers $A_i$.
### Output
- Print the number of subarray with sum divisible by $d$.
### Constraints
- $1 \le n, d \le 10^5$.
- $|A_i| \le 10^9$.
### Example
Input:
```
5 4
1 3 -2 3 -5
```
Output:
```
4
```
