Vera and the Banquet

Time limit2sMemory limit512 MB

Summary

Given a circular string S, count the number of distinct substrings appearing in any contiguous block read in either direction around the circle.

Level: Hard8 of 10
Topics: String, String matching, Sorting, Hash map
Solved: No attempts yet

Problem

Vera knows 26 recipes, each written as one lowercase letter from a to z. She is preparing a banquet of $N$ dishes placed around a circular table. Vera is lazy, so she picks the recipe of every dish independently and uniformly at random among her 26 recipes. The banquet is the string $S$ of length $N$ whose $i$ -th character is the recipe of dish $i$ . For $2 \le j \le N$ , dish $j$ sits clockwise next to dish $j-1$ , and dish 1 sits clockwise next to dish $N$ .

A sample is the sequence of recipes read off a block of consecutive dishes, either clockwise or counterclockwise. The length of a sample is at least 1 and at most $N$ . Two samples are the same when they have the same length and the same recipe at every position.

Count the distinct samples.

Input

The first line contains the integer $N$ ( $2 \le N \le 50000$ ).

The second line contains the string $S$ of $N$ lowercase letters.

Output

Print the number of distinct samples on one line.

Notes

For $N = 3$ and $S$ equal to aba, the eight distinct samples are a, b, aa, ab, ba, aba, aab, baa.

For $N = 6$ and $S$ equal to ondrej, rejo and drejon are clockwise samples, while nojer and dnojer are counterclockwise samples.

Examples3

Example 1
Input
```
3
aba
```
Expected output
```
8
```
Example 2
Input
```
6
ondrej
```
Expected output
```
66
```
Example 3
Input
```
8
waterloo
```
Expected output
```
118
```