Count subarrays with a sum divisible by k

def divisible_sums(nums, k):
    count = [0] * k
    count[0] = 1                # the empty prefix
    p = total = 0
    for x in nums:
        p += x
        r = p % k               # Python's % is already between 0 and k - 1
        total += count[r]       # read first...
        count[r] += 1           # ...then record
    return total

#include <vector>
using namespace std;

long long solve(vector<int> nums, int k) {
    vector<long long> count(k, 0);
    count[0] = 1;                        // the empty prefix
    long long p = 0, total = 0;
    for (int x : nums) {
        p += x;
        int r = (int)(((p % k) + k) % k); // C++'s % can be negative
        total += count[r];               // read first...
        count[r]++;                      // ...then record
    }
    return total;
}

class Solution {
    public long divisibleSums(int[] nums, int k) {
        long[] count = new long[k];
        count[0] = 1;                        // the empty prefix
        long p = 0, total = 0;
        for (int x : nums) {
            p += x;
            int r = (int) (((p % k) + k) % k); // Java's % can be negative
            total += count[r];               // read first...
            count[r]++;                      // ...then record
        }
        return total;
    }
}

function divisibleSums(nums, k) {
  const count = new Array(k).fill(0);
  count[0] = 1;                       // the empty prefix
  let p = 0, total = 0;
  for (const x of nums) {
    p += x;
    const r = ((p % k) + k) % k;      // JavaScript's % can be negative
    total += count[r];                // read first...
    count[r]++;                       // ...then record
  }
  return total;
}

fn solve(nums: &[i64], k: i64) -> i64 {
    let mut count = vec![0i64; k as usize];
    count[0] = 1;                        // the empty prefix
    let (mut p, mut total) = (0i64, 0i64);
    for &x in nums {
        p += x;
        let r = p.rem_euclid(k) as usize; // never negative, unlike %
        total += count[r];               // read first...
        count[r] += 1;                   // ...then record
    }
    total
}

import qualified Data.Map.Strict as M

solve :: [Int] -> Int -> Int
solve xs k = go (M.singleton 0 1) 0 0 xs
  where
    -- mod is already non-negative for positive k
    go _ _ total [] = total
    go m p total (x : rest) =
      let p' = p + x
          r  = p' `mod` k
          hit = M.findWithDefault 0 r m
      in go (M.insertWith (+) r 1 m) p' (total + hit) rest