Question
k-Divisible Subarrays
In a data analysis lab, a researcher is studying a long sequence of sensor readings collected over time.
Each reading is stored in an array nums of size n.
The researcher defines a special subarray as follows:
-
Consider any continuous segment of the array.
-
Count how many elements in that segment are divisible by a given integer k.
-
If this count itself is divisible by k, the segment is considered special.
Your task is to help the researcher determine how many special subarrays exist in the given sequence.
Input
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the size of the array and the divisor.
The second line contains KaTeX can only parse string typed expression integers — the elements of the array nums.
The second line contains KaTeX can only parse string typed expression integers — the elements of the array nums.
Output
Print a single integer — the total number of special subarrays.
Example
Input
5 2
2 3 4 6 5
Output
7
Explanation
Here, KaTeX can only parse string typed expression. We look for subarrays where the number of elements divisible by 2 is itself divisible by 2.
Valid special subarrays are:
[2, 3, 4]
[3]
[3, 4, 6]
[3, 4, 6, 5]
[4, 6]
[4, 6, 5]
[5]
Since there are 7 such subarrays, the answer is 7.
5 2
2 3 4 6 5
Output
7
Explanation
Here, KaTeX can only parse string typed expression. We look for subarrays where the number of elements divisible by 2 is itself divisible by 2.
Valid special subarrays are:
[2, 3, 4]
[3]
[3, 4, 6]
[3, 4, 6, 5]
[4, 6]
[4, 6, 5]
[5]
Since there are 7 such subarrays, the answer is 7.