В Бирмингеме все номера телефонов имеют длину $$$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$$$ баллов.
232123321124
1
242123414322143
1
В первом примере Томас предполагает, что у Артура может быть номер $$$123$$$. Следовательно, именно из этих цифр и состоит настоящий номер Артура.
Поскольку $$$K = 2$$$, то не более $$$2$$$ цифр стоят не на своих местах. Под такое описание подходит только первый номер из телефонного справочника – $$$321$$$. Для получения этого номера в номере $$$123$$$ нужно поменять местами первую и третью цифры. Во втором номере из телефонного справочника есть цифра $$$4$$$, которой в номере $$$123$$$ нет, так что этот номер точно не подойдёт.
Во втором примере также подходит только первый номер из телефонного справочника. Чтобы получить его из номера $$$1234$$$, нужно поменять местами вторую и четвёртую цифры.
Второй номер из телефонного справочника также содержит все цифры из предполагаемого номера Артура. Но чтобы его получить, потребуется поменять местами все четыре цифры, что противоречит условию $$$K = 2 \lt 4$$$.
