Adrian

Interview

Time limit1sMemory limit1024 MB

Summary

Count the substrings of a lowercase word whose letters can be rearranged into a palindrome.

Level: Medium5 of 10
Topics: Prefix sum, Bit manipulation, Hash map
Solved: No attempts yet

Problem

Young Adrian got lost wandering the remote corners of England and ran into a wizard. The wizard handed him a paper with a word written on it and asked him to count the substrings whose letters can be rearranged into a palindrome. Formally, count the index pairs $(i, j)$ with $1 \le i \le j \le$ the length of the word, such that the letters from the $i$ -th to the $j$ -th position (inclusive) can be rearranged into a palindrome. A palindrome is a word that reads the same backward, such as topot.

Input

The first and only line contains a word of at most 1,000,000 lowercase English letters.

Output

Print the number of substrings that satisfy the condition on a single line.

Hint

In the second example, the substrings are t, p, o, o, t, oo, poo (which can be rearranged into opo), oot (which can be rearranged into oto), and tpoot (which can be rearranged into topot).

Examples3

Example 1
Input
```
carobnjak
```
Expected output
```
9
```
Example 2
Input
```
tpoot
```
Expected output
```
9
```
Example 3
Input
```
abbabaab
```
Expected output
```
26
```