ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural SU contest. Petrozavodsk training camp. Summer 2008

About     Problems     Submit solution     Judge status     Standings
Contest is over

H. Monkey at the Keyboard

Time limit: 5.0 second
Memory limit: 64 MB
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?

Input

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

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

Samples

inputoutput
2
aa
6
2
ba
4
Problem Author: Igor Chevdar
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2008
To submit the solution for this problem go to the Problem set: 1677. Monkey at the Keyboard