In a distant eastern country, camel caravans still roam the deserts, with the help of which merchants transport spices, jewelry and expensive fabrics. Of course, the main goal of merchants is to sell their goods at a higher price. Recently, one of the caravans arrived at the palace of a powerful shah.
The merchants want to sell the shah n gems they brought with them. To do this, they lay them out in a row before the check, after which the check evaluates these stones and decides whether he will buy them or not. There are not very many types of precious stones in the East, only 26, so we will designate the types of stones using lowercase letters of the Latin alphabet. The shah usually evaluates the stones in the following way. He predefined several ordered pairs of stone types: (a1, b1), (a2, b2), ..., (ak, bk). He calls these pairs beautiful, and we will denote their set as P. Now we represent a row of stones sold by merchants as a string S of length n consisting of lowercase Latin letters. Shah counts the number of pairs (i,j) such that 1 ≤ i < j ≤ n, and the Si and Sj stones form a beautiful pair, that is, there is such a number 1 & le; q ≤ k that Si=aq and Sj=bq.
If the number of such pairs is large enough, then the check buys all the stones. However, this time the merchants brought so many stones that the shah cannot count this number. So he summoned his vizier and entrusted him with this calculation. Write a program that finds the answer to this problem.
Input
The first line of the input file contains integers n and k (1 ≤ n ≤ 100000, 1 ≤ k ≤ 676) the number of stones brought by the merchants and the number of couples that the Shah considers beautiful. The second line of the input file contains the string S, which describes the types of stones brought by the merchants.
K lines follow, each containing two lowercase Latin letters and describing one of the beautiful pairs of stones.
Output
Output the answer to the — the number of pairs the vizier must find.
Examples
input
7 1
abacaba
aa
output
6
input
7 3
abacaba
ab
ac
bb
output
7