题目描述

小算特别喜欢玩游戏。

这一天他突然对数字拼接产生了兴趣，例如 896 和 547 可以拼成 896547 或 547896。

当然，这是十分简单的一个问题，现在他想知道这个拼接出来的数模以 K 之后会不会等于 幸运数 ，幸运数又是什么呢？小算首先找出了一段随机的整数序列，而所有数的和对 S 取模之后就是幸运数了。是不是很简单？当然不会这么容易@_@

对于找出的这段随机的整数序列，其中任意两个数都可以进行数字拼接，只有自己不能和自己拼接，但是相同的数是可以交换顺序进行拼接的，例如 232 和 232 可以拼接成两个 232232，即视为两种拼法。现在小算想知道在进行任意可能次拼接之后，所有的拼接数对 K 取模之后会不会等于 幸运数 。

输入格式

输入包含两行，第一行包含 3 个整数 n ， K， S，第二行包含 n 个整数 NUM1, NUM2, NUM3 ... NUMn

输出格式

输出一个整数代表拼接数对 K 取模之后等于 幸运数 的拼接数的个数

例如：对于随机序列 1 2 3 4 ， K = 2， S = 5， 幸运数为 LUCKY = (1 + 2 + 3 + 4) % S = 0， 所有拼接数中只有 （12,14,24,32,34,42） 6 个数对 K 取模后等于 LUCKY = 0， 故答案为 6

数据范围

1 ≤ n ≤ 10^5
1 ≤ S ≤ K ≤ 10^5
1 ≤ num ≤ 10^10

样例

样例输入

4 2 5
1 2 3 4

样例输出

6