Divisible Sum Pairs (Divisible Sum Pairs)

Nguồn: HackerRank

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $a_0,a_1,\ldots,a_{n-1}$ và số nguyên dương $k$. Hãy đếm số cặp chỉ số $(i,j)$ thỏa

và

Mỗi cặp chỉ số chỉ được tính một lần.

Input

Dòng đầu chứa $n$ và $k$. Dòng thứ hai chứa $n$ số nguyên $a_i$.

Output

In một số nguyên: số cặp thỏa điều kiện.

Subtask

Subtask 1 (20 điểm): $2\le n\le20$, $1\le k,a_i\le20$.

Subtask 2 (30 điểm): $2\le n\le60$, $1\le k,a_i\le100$.

Subtask 3 (50 điểm): $2\le n\le100$, $1\le k\le100$, $1\le a_i\le100$.

Ví dụ

Input

6 3
1 3 2 6 1 2

Output

5

Giải thích

Có đúng $5$ cặp chỉ số có tổng chia hết cho $3$.