Count Subarrays Divisible by Length

You are given an integer array nums of length n. Values may be negative.

Count the contiguous subarrays whose sum is divisible by n, the length of the array itself.

Return that count.

Examples

Example 1

Input: nums = [3,1,2,7,4]
Output: 1
Explanation: n = 5. The only subarray whose sum is a multiple of 5 is [1,2,7] with sum 10.

Example 2

Input: nums = [0,0,0]
Output: 6
Explanation: n = 3. Every one of the 6 subarrays sums to 0, which is divisible by 3.