URI Online Judge | 3086

The Jedi Knight Guilherme

By Ezequiel Rodrigues da Silva, PUC Goiás BR Brazil

Timelimit: 1

The Jedi Knight Guilherme and his companion R2-D2 are rescuing Chancellor Palpatine from Count Dooku. When Guilherme entered in the spaceship, Dookan blocked all the doors with a shield that not even a lightsaber can cut. R2-D2 quickly accessed the system of the ship in order to turn off the shield, but the system has a defense mechanism that, to break it, the following challenge must be answered: given a string S of size n and several other strings V1, V2, … , Vm, how many palindromic substrings s exist in S such that, for all 1  i  m, Vis not a substring of s? Since the string S is too large, Guilherme is using the Force to communicate and he asks you to make a program that solves this problem.

Input

The input consists of several test cases and is finished by the end-of-file (EOF). The first line of each case contains two nonnegative integers n and m (1 ≤ n, m ≤ 100). The second line contains a string S string consisting of n alphanumeric characters. Each of the next m lines contains a string Vi (1 ≤ | Vi | ≤ 100) containing only alphanumeric characters.

Output

For each test case, print a single line containing the answer to the challenge.

Input Sample Output Sample

14 3
loreerolmippim
lore
mip
pim
8 4
fghhgfgf
f
fg
hg
gf

19
6