eolymp
bolt
Try our new interface for solving problems
Problems

ICPC and Typos

ICPC and Typos

Time limit 1 second
Memory limit 256 MiB

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 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

Input example #1
4
abcd
Output example #1
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
Author Anton Trygub
Source All-Ukrainian Collegiate Programming Contest 2021-2022, II stage