Вниз по кроличьей норе
Алисе наскучило сидеть с сестрой без дела на берегу реки; разок-другой она заглянула в книжку, которую читала сестра, но там не было ни картинок, ни разговоров.
– Что толку в книжке, – подумала Алиса, – если в ней нет ни картинок, ни разговоров?
Приключения Алисы в стране чудес (перевод Н.М. Демуровой)
– Что толку решать задачи, – подумала Алиса, – если в них нет ни картинок, ни сюжета?
Итак, Алиса юркнула в нору следом за кроликом с красными глазами, не думая о том, как же она будет выбираться обратно. Нора сначала шла прямо, ровная, как туннель, а потом вдруг круто обрывалась вниз. Не успела Алиса и глазом моргнуть, как она начала падать, словно в глубокий колодец. То ли колодец был очень глубок, то ли падала она очень медленно, только времени у нее было достаточно, чтобы прийти в себя и подумать, что же будет дальше. Сначала она попыталась разглядеть, что ждет ее внизу, но там было темно, и она ничего не увидела. Тогда она принялась смотреть по сторонам...
Стены колодца были исписаны какими-то цифрами и Алиса начала составлять из этих цифр N-значные числа и делить все эти числа на своё любимое число P. Это может показаться странным, но все числа делились на P без остатка.
– Интересно, сколько же таких чисел? – сказала Алиса вслух. – А не пролечу ли я всю землю насквозь, пока сосчитаю их количество? Вот будет смешно! Вылезаю – а люди вниз головой! Как их там зовут?.. Антипатии, кажется...
Попробуйте и вы сосчитать, сколько же таких чисел?... Так как это число может быть очень большим, то найдите ответ на задачу по модулю 1 000 000 007.
Входные данные
В первой строке входного файла записаны числа K, N и P, где K – это количество цифр, которыми были исписаны стены колодца (K ≤ 10). Во второй строке записано K различных цифр. Число N не превосходит 1000, число P не превосходит 100. Все числа в файле целые неотрицательные.
Выходные данные
В выходной файл выведите единственное число – ответ на задачу. В построении чисел каждая данная цифра может использоваться сколько угодно раз. N-значные числа должны содержать ровно N цифр, при этом первая цифра не должна равняться 0.