In this HackerEarth Mathison and the divisible trios problem solution, Mathison has discovered an old piece of paper with N integers written on it. Let's call this given sequence of numbers A. In his History class, Mathison has learned that a trio of numbers is special if and only if their sum is divisible by a mythical constant M.

Mathison tries to find out how many distinct triplets of numbers, from the piece of paper, have their sum divisible by M. Unfortunately, this problem is quite hard to crack and he needs your help.

## HackerEarth Mathison and the divisible trios problem solution.

```#include <iostream>
#include <vector>
#include <unordered_map>
#include <numeric>

using namespace std;

int main(){
ios_base::sync_with_stdio(false);

int N, M;
cin >> N >> M;

vector<int> A(N);
for (int &x: A){
cin >> x;
x %= M;
}

for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
for (int k = j + 1; k < N; k++)
if ((A[i] + A[j] + A[k]) % M == 0)

return 0;
}```

### Second solution

```import java.io.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class b
{
static FastScanner sc=new FastScanner(br);
static PrintWriter out=new PrintWriter(System.out);
static Random rnd=new Random();

static long c3(long curr)
{
return (curr*(curr-1)*(curr-2))/6;
}

public static void main(String args[]) throws Exception
{
int n=sc.nextInt(),m=sc.nextInt();int[] a=new int[n];long[] cnt=new long[m];

if(n<1|| n>200000 || m<1 || m>10000)
{
throw new Exception("Wrong");
}

for(int i=0;i<n;i++)
{
a[i]=sc.nextInt();

if(a[i]<0 || a[i]>(int)(2e9))
{
throw new Exception("Wrong");
}

cnt[a[i]%m]++;
}

long res=0;long[] p=new long[m],x=new long[m];

for(int i=0;i<m;i++)
{

long mul=(cnt[i]*p[curr]);res=(res+mul);

int curr2=(m-i-i)%m;

if(curr2<0)
{
curr2+=m;
}

for(int j=0;j<i;j++)
{
long now=(cnt[i]*cnt[j]);

p[(i+j)%m]=(p[(i+j)%m]+now);
}

int idx=(i+i)%m;

//  out.println(res);
}

for(int i=0;i<m;i++)
{
long now=(i+i+i)%m;

if(now==0)
{
res=(res+c3(cnt[i]));
}
}

out.println(res);out.close();
}
}
class FastScanner
{
StringTokenizer st;

this.in = in;
}

public String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
}
return st.nextToken();
}

public String next() throws Exception {
return nextToken().toString();
}

public int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

public long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

public double nextDouble() throws Exception {
return Double.parseDouble(nextToken());
}
}```