Infinite Repetition and Meaningful Fragment

In country A, people love repetition. A basic sentence is represented by a string of exactly $m$ lowercase letters. To show their affection for repetition, they repeat this sentence infinitely many times.

A contiguous substring (of the infinite repetition) that has the same length as a given string $s$ and is lexicographically smaller than $s$ is called a meaningful semantic fragment.

Given an integer $m$ and a string $s$ (of length $m$), count how many different basic sentences (i.e. $m$–letter strings) have the following property: when repeated infinitely, at least one fragment of length $m$ (obtained from some starting position) is lexicographically smaller than $s$.

It can be shown that for any basic sentence $T$, the set of all fragments of length $m$ in $T T$ (i.e. $T$ concatenated with itself) is exactly the set of its cyclic rotations. Hence the problem is equivalent to counting the number of $m$–letter strings whose lexicographically minimal rotation is smaller than $s$.

inputFormat

The input consists of two lines. The first line contains an integer $m$. The second line contains a string $s$ of length $m$ consisting of lowercase letters.

outputFormat

Output a single integer: the number of basic sentences (i.e. strings of length $m$) for which, after infinite repetition, there exists at least one substring of length $m$ that is lexicographically smaller than $s$.

sample

2
ba

25