Censored!

Input file

input.txt

Output file

output.txt

Time limit

1 секунда на тест

Алфавит Фриландии состоит из ровно N букв. Каждое предложение фриландского языка состоит из ровно M букв без разделителей слов. Таким образом, существует ровно NM различных фриландских предложений.

Но, после того, как в Фриландии избрали нового президента, некоторые слова, которые не нравились ему, были объявлены нецензурными и все предложения, содержащие одно из таких слов, были запрещены. Предложение S содержит слово W, если W – подстрока S, то есть существует такое ³ 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