The problem can be solved using prefix sums.

Let <code>count[i]</code> be the number of indices where <code>nums[i] % modulo == k</code> among the first <code>i</code> indices.

<code>count[0] = 0</code> and <code>count[i] = count[i - 1] + (nums[i - 1] % modulo == k ? 1 : 0)</code> for <code>i = 1, 2, ..., n</code>.

Now we want to calculate for each <code>i = 1, 2, ..., n</code>, how many indices <code>j < i</code> such that <code>(count[i] - count[j]) % modulo == k</code>.

Rewriting <code>(count[i] - count[j]) % modulo == k</code> becomes <code>count[j] = (count[i] + modulo - k) % modulo</code>.

Using a map data structure, for each <code>i = 0, 1, 2, ..., n</code>, we just sum up all <code>map[(count[i] + modulo - k) % modulo]</code> before increasing <code>map[count[i] % modulo]</code>, and the total sum is the final answer.