LSPO 2025 Finalas
April 18, 2025 Standings Problems
Problem R. 18. ABC
Input file name: standard input
Output file name: standard output
Time limit: 2 s
Memory limit: 1024 MB
You are given a string X, which consists only of the characters 'A', 'B', 'C'.
Find all integer triples (i, j, k) that satisfy the following conditions:
  • 1 \le i < j < k \le |X|
  • j-i=k-j
  • X_i=A
  • X_j=B
  • X_k=C

Input

One string X, which consists only of the characters 'A', 'B', 'C' (1 \le |X| \le 10^4).

Output

Print the number of possible triples.

Examples

standard inputstandard output
AABCC 2
ACB 0

Note

For the first test case, the valid triples are (1, 3, 5) and (2, 3, 4).