404143: GYM101431 B Vera and Banquet

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Vera and Banquettime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 Si 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.

Input

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.

Output

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

ExamplesInput
3
aba
Output
8
Input
6
ondrej
Output
66
Input
8
waterloo
Output
118
Note

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.

加入题单

上一题 下一题 算法标签: