D. Concatenated Multiples

You are given an array $\mathrm{aa,\; consisting\; of nn positive\; integers.}$

Let's call a concatenation of numbers $\mathrm{xx and yy the\; number\; that\; is\; obtained\; by\; writing\; down\; numbers xx and yy one\; right\; after\; another\; without\; changing\; the\; order.\; For\; example,\; a\; concatenation\; of\; numbers 1212 and 34563456 is\; a\; number 123456123456.}$

Count the number of ordered pairs of positions $(i,j)(i,j) (i\ne ji\ne j)\; in\; array aa such\; that\; the\; concatenation\; of aiai and ajaj is\; divisible\; by kk.$

Input

The first line contains two integers $\mathrm{nn and kk (1\le n\le 2\cdot 1051\le n\le 2\cdot 105, 2\le k\le 1092\le k\le 109).}$

The second line contains $\mathrm{nn integers a1,a2,\dots ,ana1,a2,\dots ,an (1\le ai\le 1091\le ai\le 109).}$

Output

Print a single integer — the number of ordered pairs of positions $(i,j)(i,j) (i\ne ji\ne j)\; in\; array aa such\; that\; the\; concatenation\; of aiai and ajaj is\; divisible\; by kk.$

Examples

input

Copy

6 11 45 1 10 12 11 7

output

Copy

7

input

Copy

4 2 2 78 4 10

output

Copy

12

input

Copy

5 2 3 7 19 3 3

output

Copy

0

Note

In the first example pairs $(1,2)(1,2), (1,3)(1,3), (2,3)(2,3), (3,1)(3,1), (3,4)(3,4), (4,2)(4,2), (4,3)(4,3) suffice.\; They\; produce\; numbers 451451, 45104510, 110110, 10451045, 10121012, 121121, 12101210,\; respectively,\; each\; of\; them\; is\; divisible\; by 1111.$

In the second example all $\mathrm{n(n-1)n(n-1) pairs\; suffice.}$

In the third example no pair is sufficient.

 

 题意：给出n个数，再给一个mod，然后现在有一种方法说是，可以把任意两个数连接起来，问你连接起来的对数取余mod等于0的有多少个

思路：乍一看没什么思路，暴力肯定不行，10^5的数n^2就炸了，我们就要想怎么去优化他，我们可以考虑预处理然后遍历一遍

 

我们先给出一个例子  给出n个数和一个mod，求多少对加起来mod等于0？

 这个n^2也不行，但是我们想一下如果我取余一个数=x 的话   我要什么情况才能让这个数加一个数%mod等于0

我们只有（x+y）%mod == 0     那在我们知道x的情况，我们只要找 mod-y的余数个数有多少即可

 

同理我们可以推理到这个题:因为是连接 12  34     我们相当于看成是  1200+34即可，就成功转移到了以上问题

因为连接不同的数的时候后面紧跟的0的个数不同，我们只要存下一个0到十个0所有的都用map存下即可

然后特别的，最后判断下自身加自身会不会也可以被mod为0，如果是的话-1

 

map<ll,ll> mp[11]

mp[j][x]    代表的是  j个0余数为x的个数

#include
         
          #include
          
           #include
           
            #include