405042: GYM101754 A Letters Swap

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.

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.

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

abba

2

abcabc

6

aaba

0

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.