Question
Subarrays with Sum Divisible by k
You are given an array KaTeX can only parse string typed expression of KaTeX can only parse string typed expression integers and an integer KaTeX can only parse string typed expression. Your task is to count the number of subarrays whose sum is divisible by KaTeX can only parse string typed expression.
A subarray is a contiguous part of the array.
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 given integer.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression.
The second line contains KaTeX can only parse string typed expression integers — KaTeX can only parse string typed expression.
Output
Print a single integer — the number of subarrays whose sum is divisible by KaTeX can only parse string typed expression.
Example
Input
5 3
1 2 3 4 1
Output
4
Explanation
Valid subarrays with sum divisible by 3:
(0, 1) → 1 + 2 = 3
(2, 2) → 3
(1, 3) → 2 + 3 + 4 = 9
(0, 2) → 1 + 2 + 3 = 6
Total = 4 subarrays.
5 3
1 2 3 4 1
Output
4
Explanation
Valid subarrays with sum divisible by 3:
(0, 1) → 1 + 2 = 3
(2, 2) → 3
(1, 3) → 2 + 3 + 4 = 9
(0, 2) → 1 + 2 + 3 = 6
Total = 4 subarrays.