title: Subsequences Size Three Array Whose Sum Divisible M 1
signature: subsequencesSizeThreeArrayWhoseSumDivisibleM1 :: [Integer] -> Integer -> Integer -> Double
  subsequencesSizeThreeArrayWhoseSumDivisibleM1 a n m = 
test_code: import Text.Printf
  import Control.Exception (catch, SomeException)
  import Data.Typeable
  import qualified Data.List as List
  import qualified Data.Map as Map
  import qualified Data.Set as Set
  
  -- SOLUTION CODE
  -- ============================================
  
  PLACEHOLDER_CODE_BODY
  
  -- TESTING CODE 
  -- ============================================
  validateSolution :: Double -> Double -> Bool
  validateSolution actual expected = do
      (abs (actual-expected)) < 1e-06
  
  driver :: [Integer] -> Integer -> Integer -> Double -> String
  driver a n m expected = do
      if (validateSolution (PLACEHOLDER_FN_NAME a n m) expected)
          then "PASSED"
      else "FAILED"
  
  main = do
      printf "TEST-0...%s\n" (driver ([6, 7, 13, 16, 19, 20, 0, 4, 7, 10, 15, 17, 0, 2, 8, 12, 13, 14, 0, 0, 0, 2, 2, 2, 4, 8, 10, 73, 76, 78, 87, 90, 91, 99]) (27) (21) (75.0) )
  
      printf "TEST-1...%s\n" (driver ([7, 13, 19, 15, 14, 11, 19, 4, 1, 18, 7, 5, 15, 9, 5, 11, 6, 18, 5, 19, 9, 7, 9, 19, 9, 12, 20, 12, 2, 66, 94, 12, 10, 4, 40, -72, 20, -2, -90, -90]) (29) (21) (0.0) )
  
      printf "TEST-2...%s\n" (driver ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) (29) (43) (1140.0) )
  
      printf "TEST-3...%s\n" (driver ([1, 2, 3, 37, 91]) (3) (4) (0.0) )
  
      printf "TEST-4...%s\n" (driver ([8, 6, 10, 10, 4, 2, 10, 2, 2, 10, 0, 8, 10, 86, 88]) (13) (12) (17.0) )
  
      printf "TEST-5...%s\n" (driver ([1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1]) (11) (15) (56.0) )
  
      printf "TEST-6...%s\n" (driver ([1, 2, 0, 2, 3, 0, 1, 58, 78]) (7) (4) (6.0) )
  
      printf "TEST-7...%s\n" (driver ([0, 2, 2, 12, 4, 8, 8, 6, 10, 12, 10, 4, 4, -2, -4]) (13) (14) (12.0) )
  
      printf "TEST-8...%s\n" (driver ([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) (37) (34) (286.0) )
  
      printf "TEST-9...%s\n" (driver ([27, 1, 31, 14, 20, 8, 23, 12, 15, 0, 15, 26, 3, 8, 3, 26, 15, 31, 97, 90, 1, 69, 77, 20, 68, 11, 2, 92, 50, 8, 23, 83, 76, 6, 32, 43, 92]) (18) (35) (6.0) )
  
source_py: def subsequences_size_three_array_whose_sum_divisible_m_1(A, N, M):
      ans = 0
      h = ([0] * M)
      for i in range(0, N):
          A[i] = (A[i] % M)
          h[A[i]] = (h[A[i]] + 1)
      for i in range(0, M):
          for j in range(i, M):
              rem = ((M - ((i + j) % M)) % M)
              if (rem < j):
                  continue
              if ((i == j) and (rem == j)):
                  ans = (ans + (((h[i] * (h[i] - 1)) * (h[i] - 2)) / 6))
              elif (i == j):
                  ans = (ans + (((h[i] * (h[i] - 1)) * h[rem]) / 2))
              elif (i == rem):
                  ans = (ans + (((h[i] * (h[i] - 1)) * h[j]) / 2))
              elif (rem == j):
                  ans = (ans + (((h[j] * (h[j] - 1)) * h[i]) / 2))
              else:
                  ans = (ans + ((h[i] * h[j]) * h[rem]))
          return ans
source_cpp: int subsequences_size_three_array_whose_sum_divisible_m_1(vector<int> A, int N, int M) {
    int ans = 0;
    int h [ M ] = {
      0 };
      for ( int i = 0;
      i < N;
      i ++ ) {
        A [ i ] = A [ i ] % M;
        h [ A [ i ] ] ++;
      }
      for ( int i = 0;
      i < M;
      i ++ ) {
        for ( int j = i;
        j < M;
        j ++ ) {
          int rem = ( M - ( i + j ) % M ) % M;
          if ( rem < j ) continue;
          if ( i == j && rem == j ) ans += h [ i ] * ( h [ i ] - 1 ) * ( h [ i ] - 2 ) / 6;
          else if ( i == j ) ans += h [ i ] * ( h [ i ] - 1 ) * h [ rem ] / 2;
          else if ( i == rem ) ans += h [ i ] * ( h [ i ] - 1 ) * h [ j ] / 2;
          else if ( rem == j ) ans += h [ j ] * ( h [ j ] - 1 ) * h [ i ] / 2;
          else ans = ans + h [ i ] * h [ j ] * h [ rem ];
        }
      }
      return ans;
    }