A factory logs n daily output-adjustment values (a value may be negative, representing a defect recall). Given an integer k (k >= 1), count the number of contiguous subarrays (consecutive days) whose total sum is exactly divisible by k (that is, sum mod k == 0). Print this count.
Input format
Line 1: two integers n k.
Line 2: n space-separated integers, the daily adjustment values.
Output format
A single integer: the number of contiguous subarrays whose sum is divisible by k.
Constraints
- 1 <= n <= 100000
- 1 <= k <= 100000
- -1000000 <= value <= 1000000