Censored!
Input
file |
input.txt |
Output
file |
output.txt |
Time
limit |
1 секунда на тест |
Алфавит Фриландии состоит из ровно N букв. Каждое предложение фриландского языка состоит из ровно M букв без разделителей слов. Таким образом, существует ровно NM различных фриландских предложений.
Но, после того, как в Фриландии избрали нового президента, некоторые слова, которые не нравились ему, были объявлены нецензурными и все предложения, содержащие одно из таких слов, были запрещены. Предложение S содержит слово W, если W – подстрока S, то есть существует такое k ³ 1, что S[k] = W[1], S[k+1] = W[2], …, S[k+len(W)-1] = W[len(W)], где k+len(W)-1 £ M и len(W) обозначает длину W. Каждого, кто использует запрещенное предложение, садят в тюрьму на 10 лет.
Найдите, сколько различных предложений могут сейчас
использовать фриландцы без риска быть посаженными в тюрьму за их использование.
Входные данные
Первая строка входного файла три целых числа: N — количество букв в фриландском алфавите, M — длина всех фриландских предложений и P — количество запрещенных слов (1 £ N £ 50, 1 £ M £ 50, 0 £ P £ 10).
Вторая строка содержит ровно N различных символов — буквы фриландского алфавита (символы с ASCII-кодами большими 32).
Следующие P строк содержат запрещенные слова, каждое не длиннее min(M, 10) символов, содержащие только буквы фриландского алфавита.
Выходные данные
Выведите только одно целое число – количество различных предложений, которые фриландцы могут безопасно использовать.
Пример
Input.txt |
output.txt |
2 3 1 ab bb |
5 |
3 2 0 012 |
9 |
3 3 3 QWE QQ WEE Q |
7 |
2 50 4 AB AA AB BA BB |
0 |