pqr

You are given an array $A$ of $N$ numbers and an integer $K$.

Write a program that counts the triples $(p, q, r)$ with $0 \le p < q < r < N$ such that $A[p] \times A[q] \times A[r]$ is divisible by $K$.

The first line contains $N$ and $K$, separated by a space. ($3 \le N \le 2\,000$, $1 \le K \le 1\,000\,000$)

The second line contains the elements of $A$ in order from $A[0]$ to $A[N-1]$. ($1 \le A[i] \le 100\,000\,000$)

Print the number of triples $(p, q, r)$ with $0 \le p < q < r < N$ such that $A[p] \times A[q] \times A[r]$ is divisible by $K$.