4. Бирмингем
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В Бирмингеме все номера телефонов имеют длину $$$L$$$ и состоят только из цифр от 0 до 9. Томас Шелби собрался позвонить своему брату Артуру, но понял, что не помнит его точный номер.

У Томаса прекрасная память на цифры, так что он совершенно точно помнит все цифры номера Артура. Но в их порядке он совсем не уверен. Томас попытался составить из цифр, которые он помнит, номер Артура и записал его на листке бумаги. Он полагает, что мог перепутать позиции некоторых цифр, но таких цифр, которые стоят в его записи не на своих местах, не более $$$K$$$.

Телефонные справочники в Бирмингеме содержат не настоящие имена жителей, а псевдонимы, которые сообщили владельцы номеров. К огорчению Томаса, он не знает, какой псевдоним принадлежит его брату. Поэтому Томас принял решение просмотреть все $$$N$$$ номеров и выбрать те из них, которые могут оказаться номером Артура.

Определите количество таких номеров.

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

В трёх строках вводятся три числа $$$N$$$, $$$L$$$, $$$K$$$ ($$$1 \leq N \cdot L \leq 10^{5}$$$, $$$2 \leq K \leq L$$$) — количество номеров в справочнике Томаса, длина всех номеров и максимальное количество цифр, стоящих не на своих местах в том номере, который помнит Томас.

В четвёртой строке написан возможный номер Артура, записанный Томасом.

В следующих $$$N$$$ строках идут телефонные номера из телефонного справочника.

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

В первой строке выведите одно целое число — количество номеров, которые могут оказаться номером Артура.

Система оценки

Решения, правильно работающие при $$$L \leq 10, K \leq 5$$$, будут оцениваться в $$$30$$$ баллов.

Решения, правильно работающие при условии, что в номерах телефонов встречаются только цифры 1 и 2, будут оцениваться в $$$40$$$ баллов.

Примеры
Входные данные
2
3
2
123
321
124
Выходные данные
1
Входные данные
2
4
2
1234
1432
2143
Выходные данные
1
Примечание

В первом примере Томас предполагает, что у Артура может быть номер $$$123$$$. Следовательно, именно из этих цифр и состоит настоящий номер Артура.

Поскольку $$$K = 2$$$, то не более $$$2$$$ цифр стоят не на своих местах. Под такое описание подходит только первый номер из телефонного справочника – $$$321$$$. Для получения этого номера в номере $$$123$$$ нужно поменять местами первую и третью цифры. Во втором номере из телефонного справочника есть цифра $$$4$$$, которой в номере $$$123$$$ нет, так что этот номер точно не подойдёт.

Во втором примере также подходит только первый номер из телефонного справочника. Чтобы получить его из номера $$$1234$$$, нужно поменять местами вторую и четвёртую цифры.

Второй номер из телефонного справочника также содержит все цифры из предполагаемого номера Артура. Но чтобы его получить, потребуется поменять местами все четыре цифры, что противоречит условию $$$K = 2 \lt 4$$$.