You are given a string s of length n.

A substring is called valid if its characters can be rearranged to form a palindrome.

For example, aab is valid because it can be rearranged as aba. But abc is not valid because it cannot be rearranged to form a palindrome.

Your task is to count the number of non-empty valid substrings of s.

The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.

The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression.

Print a single integer — the number of non-empty substrings whose characters can be rearranged to form a palindrome.