Use prefix sums to calculate the subarray sums.

Suppose you know the remainder for the sum of the entire array. How does removing a subarray affect that remainder? What remainder does the subarray need to have in order to make the rest of the array sum up to be divisible by k?

Use a map to keep track of the rightmost index for every prefix sum % p.