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