public class Solution {
    Dictionary<int, int> dic = new Dictionary<int, int>();
    public int SubarraysDivByK(int[] A, int K)
    {
        int[] B = new int[A.Length+1];
        int temp = 0;
        B[0] = 0;
        dic.Add(0, 1);
        for (int i = 0; i < A.Length; i++)
        {
            B[i + 1] = B[i] + A[i];
            temp = B[i + 1] % K;
            if (temp < 0)
            {
                temp += K;
            }
            if (dic.ContainsKey(temp))
            {
                dic[temp]++;
            }
            else
            {
                dic.Add(temp, 1);
            }
        }
        int result = 0;
        foreach (var item in dic)
        {
            result += item.Value * (item.Value - 1) / 2;
        }
        return result;
    }
}