Задача C. Неприступный форт ≡
| Автор: | Антон Карабанов | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 64 Мб | |
| Выходной файл: | Стандартный выход | |||
| Максимальный балл: | 100 |
Условие
Команда игроков участвует в соревновании "Форт Боярд". После долгой борьбы за ключи и подсказки, тяжелых конкурсов и загадок старца Фура, побегов из тюрьмы и совета Теней, участники игры добрались до Сокровищницы. Теперь они должны разгадать кодовое слово и обозначить составляющие его буквы при помощи пушечных ядер на алфавитном полу Сокровищницы. Если предложенный вариант окажется правильным, игроки получают доступ к золотым монетам, и могут попытаться вынести наружу как можно большее их количество.
Капитан команды считает, что загаданное организаторами кодовое слово - s. Помогите ему определить количество способов расставить ядра на полу сокровищницы для проверки.
Формат входных данных
Первая строка входного файла содержит одно английское слово s, записанное строчными буквами. Вторая строка содержит два натуральных числа, записанных через пробел: n и m - количество строк и столбцов на алфавитном полу. В следующих n строках записано по m строчных английских букв - описание пола.
Формат выходных данных
Выведите одно неотрицательное целое число - ответ на задачу. Гарантируется, что ответ не превысит 1018.
Ограничения
1 ≤ n, m ≤ 20
1 ≤ len(s) ≤ 50
Система оценки и описание подзадач
Баллы за каждый тест начисляются независимо.
Пояснение к примеру
В примере участники могут выбрать одно из двух положений ядра для символа 'u' и одно из двух положений для символа 'e'. Остальные символы можно выбрать единственным образом.
Примеры тестов
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 |
|
|