Названия стихотворений
Названия стихотворений
На недавно прошедшем референдуме смешарики приняли поправки к статье «Названия стихотворений» закона «О Защите Авторских Прав». Раньше закон требовал, чтобы называния стихотворений были последовательностями из 0 и 1. А сейчас необходимо, чтобы название каждого нового стихотворения не только состояло из 0 и 1, но и не содержало в себе названий других, уже опубликованных произведений.
После референдума, смешарики опубликовали на своем сайте список названий уже существующих произведений. И с появлением каждого нового стихотворения решили обновлять этот список.
Узнав о таких изменениях в законодательстве, Бараш решил называть все свои шедевры последовательностями длины K
. Он зашел на сайт смешариков и увидел, что в списке уже есть N
чужих произведений. Ему стало интересно, сколько еще стихотворений он сможет сочинить, не нарушая новый закон. Начав считать, Бараш понял, что это слишком сложно и ему с этим не справиться. Помогите Барашу определить, сколько стихотворений он сможет сочинить. Бараш подозревает, что таких стихотворений будет слишком много, поэтому он просит вывести не все число, а взятое по модулю P
.
Входные данные
В первой строке даны три числа N
, K
(K ≤ 1000
) и P
(P ≤ 2 * 109
). В последующих N
строках записан список названий. Каждое название представляет собой последовательность нулей и единиц. Длина слов не превышает 15. Известо, что до принятия закона некоторые названия стихотворений могли совпадать, но из списка их не изъяли.
Выходные данные
Вывести число, равное количеству стихотворений по модулю P
, которые сможет сочинить Бараш, не меняя своего правила о длине названия и не нарушая закон.
2 3 100 10 01
2