The “Entertaining math” showmen decided to ensure their audience in the well-known fact that a monkey randomly pressing keyboard buttons will sooner or later type the required word according to the probability theory.

The monkey taken to the shooting from the city zoo already can type — every second she types one of N first letters of English alphabet with equal probability. Fortunately, the word prepared by the showmen also contains some of these N letters only.

However, prior to giving a keyboard to the monkey, the showmen want to calculate the time it would take her to finish the job. More precisely, after how many seconds the given word will appear in the typed string for the first time?

The first line contains an integer N — the number of letters the monkey can type (1 ≤ N ≤ 26). The second line contains a word proposed by the showmen. The word can contain only the first N lowercase Latin letters. Its length is positive and doesn't exceed 30000.

Output the expected time the monkey will need to type a word, rounded down to the nearest integer.