Problem Description

You are given an array $A_1, A_2, \cdots, A_n$ of length $n$. You may choose two numbers $A_i$ and $A_j$ ($i \neq j$), then concatenate $A_i$ and $A_j$ in order to form a new integer. For example, 12 and 345 can be concatenated into 12345 or 34512. Note that swapping the order of $A_i$ and $A_j$ is always considered as $2$ different ways of concatenation, even when $A_i = A_j$.

Please compute how many concatenations result in an integer that is a multiple of $K$.

Input Format

The first line contains $2$ integers $n$ and $K$.

The second line contains $n$ integers $A_1, A_2, \cdots, A_n$.

Output Format

Output one integer representing the answer.

4 2
1 2 3 4

6

Hint

For all test cases, $1 \le n \le 10^5$, $1 \le k \le 10^5$, and $1 \le A_i \le 10^9$.

Lanqiao Cup 2020, First Round Provincial Contest, Group B, Problem I.

Translated by ChatGPT 5