시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB111100.000%

문제

В одной далекой восточной стране до сих пор по пустыням ходят караваны верблюдов, с помощью которых купцы перевозят пряности, драгоценности и дорогие ткани. Разумеется, основная цель купцов состоит в том, чтобы подороже продать имеющийся у них товар. Недавно один из караванов прибыл во дворец одного могущественного шаха.

Купцы хотят продать шаху $n$ драгоценных камней, которые они привезли с собой. Для этого они выкладывают их перед шахом в ряд, после чего шах оценивает эти камни и принимает решение о том, купит он их или нет.

Видов драгоценных камней на Востоке известно не очень много --- всего 26, поэтому мы будем обозначать виды камней с помощью строчных букв латинского алфавита. Шах обычно оценивает камни следующим образом. 

Он заранее определил несколько упорядоченных пар типов камней: $(a_1, b_1)$, $(a_2,b_2)$, \ldots, $(a_k,b_k)$. Эти пары он называет красивыми, их множество мы обозначим как $P$. Теперь представим ряд камней, которые продают купцы, в виде строки $S$ длины $n$ из строчных букв латинского алфавита. Шах считает число таких пар $(i,j)$, что $1 \le i < j \le n$, а камни $S_i$ и $S_j$ образуют красивую пару, то есть существует такое число $1 \le q \le k$, что $S_i = a_q$ и $S_j = b_q$. 

Если число таких пар оказывается достаточно большим, то шах покупает все камни. Однако в этот раз купцы привезли настолько много камней, что шах не может посчитать это число. Поэтому он вызвал своего визиря и поручил ему этот подсчет.

Напишите программу, которая находит ответ на эту задачу.

입력

Первая строка входного файла содержит целые числа $n$ и $k$ ($1 \le n \le 100000$, $1 \le k \le 676$) --- число камней, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку $S$, описывающую типы камней, которые привезли купцы.

Далее следуют $k$ строк, каждая из которых содержит две строчных буквы латинского алфавита и описывает одну из красивых пар камней.

출력

В выходной файл выведите ответ на задачу --- количество пар, которое должен найти визирь.

예제 입력 1

7 1
abacaba
aa

예제 출력 1

6

예제 입력 2

7 3
abacaba
ab
ac
bb

예제 출력 2

7