ICPC and Typos
ICPC and Typos
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 ofshell
)One extra letter was accidentally inserted (for example,
horny
is written instead ofhorn
)One letter was accidentally replaced with another (for example,
ictc
is written instead oficpc
)
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 sexactly one typo?
Input data
The first line contains a single integer n (1 \le n \le 26) — the size of the alphabet.
The second line contains a string s (2 \le |s| \le 100000), which consists only of the first n letters of the Latin alphabet.
Output data
Output the number of distinct words that you can obtain by making in sexactly 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
.
Examples
4 abcd
32
Note
From the string abcd
from the sample we can obtain the following strings:
abc abd acd bcd
aacd abad abbd abca
abcb abcc abdd accd
adcd bbcd cbcd dbcd
aabcd abacd abbcd abcad
abcbd abccd abcda abcdb
abcdc abcdd abdcd acbcd
adbcd babcd cabcd dabcd