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