A string is called "palindrome-like" if it can be rearranged in any way to become a palindrome. eg : aabb is a palindrome as it can be rearranged like abba. For any string you are allowed to change any number of characters in it to make it "palindrome-like". Let this amount for any string be "cost" Find the total sum of palindrome transformation cost of all the substrings of the given string.

eg:
abca ->
    "a", "b", "c", "a", with cost = 0
    "ab", cost = 1, we can change 'b' to 'a' and it becomes "aa" which is a palindrome.
    "abc", cost = 1, we can change 'b' to 'c' and it can be rearranged to "cac" which is a palindrome.
    "abca", cost = 1, we can change 'b' to 'c' and it becomes "acca" which is a palindrome.
    "bc", cost = 1, we can change 'b' to 'c' and it becomes "cc" which is a palindrome.
    "abc", cost = 1, we can change 'b' to 'c' and it can be rearranged to "cac" which is a palindrome.
    "abca", cost = 1, we can change 'b' to 'c' and it becomes "acca" which is a palindrome.
    "bc", cost = 1, we can change 'b' to 'c' and it becomes "cc" which is a palindrome.
    "bca", cost = 1, we can change 'c' to 'a' and it can be rearranged to "aba" which is a palindrome.
    "ca", cost = 1, we can change 'c' to 'a' and it becomes "aa" which is a palindrome.

constraint: n <= 10**5