Задача E. Драгоценные камни ≡

Условие

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

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

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

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

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

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

Формат входного файла

Первая строка входного файла содержит целые числа n и k — число камней, которые привезли купцы и число пар, которые шах считает красивыми. Вторая строка входного файла содержит строку S, описывающую типы камней, которые привезли купцы.

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

Формат выходного файла

Ограничения

1 ≤ n ≤ 100000

1 ≤ k ≤ 676

Примеры тестов

7 1
abacaba
aa

6

7 3
abacaba
ab
ac
bb

7