ICPC та друкарські помилки#10828

ICPC та друкарські помилки

1 секунда

256 мегабайтів

Дуже легка

Друкарські помилки — це дуже важлива частина умов задач ICPC. Дослідницький відділ ICPC виявив, що існує $3$ основні категорії друкарських помилок:

Одна літера слова була випадково пропущена (наприклад, написано sell замість shell)
Одна зайва літера була випадково додана (наприклад, написано horny замість horn)
Одна літера була випадково замінена іншою (наприклад, написано ictc замість icpc)

Зараз дослідницький відділ ICPC розглядає алфавіт, що складається з перших $n$ латинських літер, і слово $s$ . Вони задаються питанням: скільки різних слів можна отримати, зробивши в $s$ рівно одну друкарську помилку?

Вхідні дані

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 26$ 1 \le n \le 26) — розмір алфавіту.

Другий рядок містить рядок $s$ ( $2 \leq ∣ s ∣ \leq 100000$ 2 \le |s| \le 100000), який складається виключно з перших $n$ літер латинського алфавіту.

Вихідні дані

Виведіть кількість різних слів, які можна отримати, зробивши в $s$ рівно одну друкарську помилку.

Зверніть увагу, що слово з помилкою також має містити виключно літери з перших $n$ літер латинського алфавіту. Наприклад, для $n = 3$ n = 3 та $s =$ cab неможливо отримати dab, допустивши помилку в літері c.

Приклади

Приклад 1

Примітка

З рядка abcd зі зразка ми можемо отримати наступні рядки:

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