Ваша задача — вычислить количество троек (i, j, k) таких, что i ≤ j < k и s[i..j] — палиндром и s[j+1 .. k] — палиндром.

Вход содержит строку из n строчных латинских букв (1 ≤ n ≤ 3 · 10⁵).

Выведите количество требуемых троек.