Підрядки

Є рядок $s$ довжини $n$, який складається лише з літер A, T, C, G.

Кажуть, що два рядки однакової довжини компліментарні, якщо на кожній позиції символи утворюють одну з таких пар: \texttt{A} \leftrightarrow \texttt{T},\quad \texttt{C} \leftrightarrow \texttt{G}. Інакше кажучи, A підходить тільки до T, T — тільки до A, C — до G, і навпаки.

Наприклад, рядки ATCG і TAGC компліментарні, оскільки: \texttt{A-T},\ \texttt{T-A},\ \texttt{C-G},\ \texttt{G-C}.

Рядок називається перестановочно компліментарним, якщо існує перестановка його літер, компліментарна самому рядку.

Тепер завдання. Порахуйте кількість пар (i, j): 1 \le i \le j \le n, що підрядок s[i:j] є перестановочно компліментарним.

Підрядок рядка $s$ з позначенням s[i:j] — це рядок, що складається з символів s_i, s_{i+1}, \ldots, s_j.