Typos are a very important part of ICPC problem statements. ICPC research department found out that there exist 3 main categories of typos:
One letter of the word was accidentally skipped (for example, sell
is written instead of shell
)
One extra letter was accidentally inserted (for example, horny
is written instead of horn
)
One letter was accidentally replaced with another (for example, ictc
is written instead of icpc
)
ICPC research department now considers an alphabet consisting of first n Latin letters and a word s. They wonder: how many distinct words can you obtain by making in s exactly one typo?
The first line contains a single integer n (1≤n≤26) — the size of the alphabet.
The second line contains a string s (2≤∣s∣≤100000), which consists only of the first n letters of the Latin alphabet.
Output the number of distinct words that you can obtain by making in s exactly one typo.
Note that the word with typos can contain only letters among the first n letters of the Latin alphabet, too. For example, for n=3 and s= cab
you can't obtain dab
by mistyping c
.
From the string abcd
from the sample we can obtain the following strings: