Областная олимпиада по информатике 2019 года за 11 класс | Казахстанские олимпиады

Задача C. Хан и массив

Ограничение по времени Ограничение по памяти
2 секунды 512 мегабайт

Хан на день рождения получил массив из nn элементов. И начал с ним играться. Он взял каждый элемент и записал mm раз. Также у Хана есть любимое простое число PP. Ему стало интересно, сколько существует подпоследовательностей, которые в сумме делятся на PP. Помогите Хану узнать сколько таких подпоследовательностей.

Формат входного файла

В первой строке даны три целых числа nn, mm, PP через пробел — размер массива Хана; количество раз, которое он записывает каждое число в массиве; и простое число соответственно (1<=n<=105,1<=m<=109,1<=P<=103)(1 <= n <= 10^5, 1 <= m <= 10^9, 1 <= P <= 10^3).

Во второй строке даны nn целых чисел a1,a2,...,ana_1, a_2, ..., a_n — полученный Ханом массив на его день рождения (1<=ai<=109)(1 <= a_i <= 10^9).

Формат выходного файла

Выведите одно число — количество подпоследовательностей, которые в сумме делятся на PP. Так как это число может быть большим, выведите его остаток от деления на 10000000071000000007.

Примеры

Вход

3 2 5
3 7 4

Выход

11