A. Замена букв
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана непустая последовательность из букв «a», «b» и «c». Требуется посчитать количество способов выбрать две различные буквы в последовательности (то есть две разные по значению буквы, одинаковые буквы на разных позициях выбирать не разрешается) и поменять их местами, чтобы получившаяся последовательность была правильной.

Правильная последовательность букв определяется следующим образом:

  • Пустая последовательность является правильной.
  • Если A — правильная последовательность, то aAa, bAb и cAc также являются правильными.
  • Если A и B — правильные последовательности, то AB (конкатенация A и B) также правильная.
  • Последовательности, которые невозможно получить при помощи операций, описанных выше, не являются правильными.
Входные данные

В единственной строке записана непустая последовательность из символов «a», «b», «c». Длина последовательности не превосходит 100 000 символов.

Выходные данные

Выведите одно число — количество спобов поменять местами две различные буквы, чтобы получившаяся последовательность была правильной.

Примеры
Входные данные
abba
Выходные данные
2
Входные данные
abcabc
Выходные данные
6
Входные данные
aaba
Выходные данные
0
Примечание

В первом примере заменой букв можно получить правильные последовательности «aabb» и «bbaa». Обратите внимание, что исходная последовательность уже может быть правильной, но оставлять её без изменений нельзя.

Во втором примере можно получить правильные последовательности «abbacc», «abccba», «accabb», «aacbbc», «bbcaac» и «cbaabc».

В третьем примере количество букв «a» нечётно, поэтому правильную последовательность получить нельзя.