K. Sample Heat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Blessing It -remix
Nujabes ft. Substantial and Pase Rock, Metaphorical Music

As a music producer, Mai has been trying to get her career off the ground! She has $$$n$$$ samples on a record disk. The disk is represented as a string $$$s$$$ of $$$n$$$ characters, where each sample is labeled with some lowercase character 'a'-'z'. As part of creating a beat, Mai will pick some substring of samples to use as the foundation of their beat. Mai prefers sounds that have a symmetric sound to them, so the substring she extracts must be a palindrome.

The heat of a substring of samples is the sum of the IDs used, where 'a' corresponds to a value of 1, 'b' corresponds to a value of 2, and so forth. If an ID appears multiple times, it is counted multiple times in this sum. Mai wants to compute how valuable the record is, so she wants to compute the sum of the heats of all distinct valid substring of samples. Please help her do so!

A palindrome is a string that reads the same forwards and backwards. For example, "aa" and "abacaba" are both palindromes, while "abb" and "utpc" are not.

Two substring are distinct if they have different lengths or at least one position differs between the two substring.

Input

The first line contains a single integer $$$n\ (1 \leq n \leq 10^5)$$$ — the number of samples.

The second line contains a single string $$$s$$$ of length $$$n$$$, comprising of only the characters 'a'-'z' — the representation of the samples on the disk.

Output

Output a single integer — the sum of the heats of each distinct palindromic substring.

Example
Input
5
aabaa
Output
15
Note

For the input "aabaa", the heats of the palindromic substrings are:

  • "a" with a heat of $$$1$$$
  • "b" with a heat of $$$2$$$
  • "aa" with a heat of $$$2$$$
  • "aba" with a heat of $$$4$$$
  • "aabaa" with a heat of $$$6$$$