404143: GYM101431 B Vera and Banquet

Vera knows 26 recipes, each represented by a lowercase letter from a to z. She is preparing a banquet consisting of N dishes arranged around a circular table. Since Vera is lazy, each dish is independently and uniformly randomly chosen from one of her 26 recipes. The banquet can be represented as a string S of length N where S_i is the recipe of dish i (1 ≤ i ≤ N). Dish j is clockwise to dish j - 1 for 2 ≤ j ≤ N and dish 1 is clockwise to dish N.

A sample is the sequence of recipes in a consecutive section of dishes in either clockwise or counter-clockwise direction.

Vera wonders how many different samples there are. Two samples are the same if they have the same length and the same recipe at every position.

Line 1 contains integer N (2 ≤ N ≤ 50000).

Line 2 contains string S of N lowercase letters. It is guaranteed that S represents a banquet created by the described process.

Print one line with one integer, the number of different samples.

3
aba

8

6
ondrej

66

8
waterloo

118

For the first example, the eight different samples are a, b, aa, ab, ba, aba, aab, baa.

For the second example, rejo, drejon are clockwise samples and nojer, dnojer are counter-clockwise samples.