Hypergnome planet is famous for its Great Universal Games between gnomes — the Games between gnomes from each part of the galaxy in various disciplines.
The most popular discipline in the Games is the Hyperdrome discipline. The rules are the follows: one string of length n is given to all gnomes. The gnomes shall find, as fast as they can, the total number of Hyperdrome substrings — such strings that characters inside the string can be rearranged to get a palindrome.
Substring is defined as a sequence of characters from position i to position j inclusive, where 1 ≤ i ≤ j ≤ n. Substrings with different pairs of positions (i, j) are considered different regardless of their contents.
Palindrome is defined as a string x1x2…xl, where xi = xl−i+1 for all 1 ≤ i ≤ l.
Judges choose a string and your task is to help them find the answer.
The gnome alphabet consists of lowercase and uppercase English letters — ‘a’–‘z’ and ‘A’–‘Z’ where letters in different case are considered to be different letters.