Вниз по кроликовій норі
Алісі надокучило сидіти з сестрою просто так на березі річки; разок-другий вона заглянула у книжку, яку читала сестра, але там не було ні картинок, ні розмов.
– Який толк у книжці, – подумала Аліса, – якщо в ній немає ні картинок, ні розмов?
Пригоди Аліси у країні чудес (переклад Н.М. Демурової)
– Який толк розв'язувати задачі, – подумала Аліса, – якщо в них немає ні картинок, ні сюжету?
Отже, Аліса юркнула у нору слідком за кроликом з червоними очима, не думаючи про те, як же вона буде вибиратись назад. Нора спочатку йшла прямо, рівна, як тунель, а потім раптом стрімко обривалась донизу. Не вспіла Аліса і оком моргнути, як вона почала падати, ніби у глибокий колодязь. Чи то колодязь був дуже глибокий, чи то падала вона дуже повільно, тільки часу у неї було вдосаль, щоб прийти до тями і подумати, що ж буде далі. Спочатка вона спробувла розгледіти, що чекає її внизу, але там було темно, і вона нічого не побачила. Тоді вона прийнялась розглядувати по сторонам...
Стіни колодязя були списані якимись цифрами і Аліса почала складати з цих цифр N-значні числа і ділити всі ці числа на своє любиме число P. Це може показатись дивним, але всі числа ділились на P без остачі.
– Цікаво, скільки ж таких чисел? – сказала Алиса вголос. – А чи не пролечу я всю землю наскрізь, доки порахую їх кількість? Оце буде смішно! Вилажу – а люди вниз головою! Як їх там зовуть?.. Антипатії, здається...
Спробуйте і ви порахувати, скільки ж таких чисел?... Так як це число може бути дуже великим, то знайдіть відповідь до задачі по модулю 1 000 000 007.
Вхідні дані
У першому рядку вхідного файлу записані числа K, N і P, де K – це кількість цифр, якими були списані стіни колодязя (K ≤ 10). У другому рядку записано K різних цифр. Число N не перевищує 1000, число P не перевищує 100. Всі числаув файлі цілі невід'ємні.
Вихідні дані
У вихідний файл виведіть єдине число – відповідь до задачі. У побудові чисел кожна задана цифра може використовуватись скільки завгодно раз. N-значнв числа повинні містити рівно N цифр, при цьому перша цифра не повинна дорівнювати 0.