AT_abc433_d [ABC433D] 183183

For positive integers $ x,y $ , define $ f(x,y) $ as follows: - The value obtained by interpreting $ x,y $ in decimal notation without leading zeros as strings, concatenating them in this order to obtain a string $ S $ , and then interpreting $ S $ as an integer in decimal notation. For example, $ f(12,3) = 123 $ and $ f(100,40)=10040 $ . You are given positive integers $ N,M $ and a sequence of $ N $ positive integers $ A=(A_1,A_2,\ldots,A_N) $ . Find the number of pairs of integers $ (i,j) $ that satisfy all of the following conditions. - $ 1\le i,j\le N $ - $ f(A_i,A_j) $ is a multiple of $ M $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the number of pairs of integers $ (i,j) $ that satisfy all the conditions.

### Sample Explanation 1 - When $ (i,j)=(1,1) $ : $ f(A_1,A_1)=22 $ is a multiple of $ 11 $ . - When $ (i,j)=(1,2) $ : $ f(A_1,A_2)=242 $ is a multiple of $ 11 $ . - When $ (i,j)=(2,1) $ : $ f(A_2,A_1)=422 $ is not a multiple of $ 11 $ . - When $ (i,j)=(2,2) $ : $ f(A_2,A_2)=4242 $ is not a multiple of $ 11 $ . From the above, the pairs of integers that satisfy all the conditions are $ (i,j)=(1,1),(1,2) $ , which is two pairs. Thus, output $ 2 $ . ### Constraints - $ 1\le N\le 2\times 10^5 $ - $ 1\le M\le 10^9 $ - $ 1\le A_i\le 10^9 $ - All input values are integers.