e-olymp
Задачі

Назви віршів

Назви віршів

prb210 На нещодавно проведеному референдумі смішарики прийняли поправки до статтіе «Назви віршів» закону «Про Захист Авторських Прав». Раніше закон вимагав, щоб назвн віршів були послідовностями з 0 і 1. А зараз необхідно, щоб назва кажного нового вірша не тільки складалась з 0 і 1, але і не містила в собі нази інших, вже опублікованих творів.

Після референдуму, смішарики опублікували на своєму сайті список назв вже існуючих творів. І з появою кожного нового вірша вирішили оновлювати цей список.

Взнавши про такі зміни в законодавстві, Бараш вирішив називати всі свої шедеври послідовностями довжини К. Він зайшов на сайт смішариків і побачив, що в списку вже є N чужих творів. Йому стало цікаво, скільки ще віршів він зможе написати, не порушуючи новий закон. Почавши рахувати, Бараш зрозумів, що це занадто складно і йому з цим не справитись. Допоможіть Барашу визначити, скільки віршів він зможе написати. Бараш підозрює, що таких віршів буде занадто багато, тому він просить вивести не все число, а взяте по модулю P

.

Вхідні дані

У першому рядку задано три числа N, К (K1000) і P (P2*109). У наступних N рядках записано список назв. Кожна назва являє собою послідовність нулів та единиць. Довжина слів не перевищує 15. Відомо, що до прийняття закону деякі назви віршів могли співпадати, але зі списку їх не видалили.

Вихідні дані

Вивести число, рівне кількості віршів по модулю P, які зможе написати Бараш, не змінюючи своего правила про довжину назв та не порушуючи закон.

Ліміт часу 3 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
2 3 100
10
01
Вихідні дані #1
2