e-olymp
Problems

Names of poems (RU)

Names of poems (RU)

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

После референдума, смешарики опубликовали на своем сайте список названий уже существующих произведений. И с появлением каждого нового стихотворения решили обновлять этот список.

Узнав о таких изменениях в законодательстве, Бараш решил называть все свои шедевры последовательностями длины К. Он зашел на сайт смешариков и увидел, что в списке уже есть N чужих произведений. Ему стало интересно, сколько еще стихотворений он сможет сочинить, не нарушая новый закон. Начав считать, Бараш понял, что это слишком сложно и ему с этим не справиться. Помогите Барашу определить, сколько стихотворений он сможет сочинить. Бараш подозревает, что таких стихотворений будет слишком много, поэтому он просит вывести не все число, а взятое по модулю P

.

Входные данные

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

Выходные данные

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

Time limit 3 seconds
Memory limit 64 MiB
Input example #1
2 3 100
10
01
Output example #1
2