A. Letters Swap
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a non-empty sequence of letters "a", "b", and "c". Find the number of ways to swap two distinct letters (distinct by value, you are not allowed to pick two equal letters at distinct positions) in this sequence so that the resulting sequence is correct.

A correct sequence of letters is defined as follows:

  • An empty sequence is correct.
  • If A is a correct sequence, then aAa, bAb, and cAc are correct as well.
  • If A and B are correct sequences, then AB (concatenation of A and B) is correct as well.
  • Sequences that cannot be obtained by rules above are not correct.
Input

The only line contains a non-empty sequence of characters "a", "b", and "c". The length of the sequence does not exceed 100 000 characters.

Output

Print one number — the number of ways to swap two distinct letters so that the resulting sequence is correct.

Examples
Input
abba
Output
2
Input
abcabc
Output
6
Input
aaba
Output
0
Note

In the first sample we can obtain correct sequences "aabb" and «bbaa» by swapping letters. Note that the initial sequence may be correct, but it is not allowed to leave it unchanged.

In the second sample we can obtain correct sequences "abbacc", "abccba", "accabb", "aacbbc", "bbcaac", and "cbaabc".

In the third sample the number of "a" letters is odd, hence making a correct sequence is impossible.