Chưng is a big fan of cream puffs, and he has created delicious cream puffs for Quýt. Chưng has come up with 26 different flavors of cream puffs, each represented by a lowercase letter (from 'a' to 'z').One day, Chưng successfully made n different cream puffs and planned to bring them over to Quýt's house. However, for Chưng, cream puffs not only have to taste good but also look beautiful. So, he decided to combine consecutive cream puffs into a symmetric cream puff.

A symmetric cream puff is a sequence of consecutive cream puffs with an even length, where the sequence of flavor letters forms a palindromic string. Additionally, another way to create a symmetric cream puff is by combining several smaller symmetric cream puffs in sequence. For example: "aa"and "aabaab"are symmetric cream puffs, but "Quýt"and "Chưng"are not. Since Chưng made too many cream puffs, he doesn't know which symmetric cream puff to give to Quýt. Help him count how many ways he can form symmetric cream puffs using the ~n~ available cream puffs.

Input

• The first line contains a single integer N where 1 ≤ N ≤ 5 × 105, representing the number of cream puffs, numbered from 1 to ~n~.

• The second line contains ~n~ lowercase English letters, where the ~i_{th}~ letter represents the flavor of the ~i_{th}~ cream puff.

Output

• A single line containing the number of ways to form symmetric cream puffs from the given cream puffs.

Sample Input 1

6
abaaba

Sample Ouput 1

3

Note: We will have symmetrical ice creams: "aa", "baab"and "abaaba".