Count Palindromic Subsequences of Length 3

You are given a string s and must count the number of palindromic subsequences of length 3.

A subsequence of length 3 is defined by three indices i, j, k with 0 ≤ i < j < k < n (where n is the length of s), such that the characters at positions i and k are equal. In other words, the subsequence s[i] s[j] s[k] is palindromic if it satisfies:

$$ s[i] = s[k] $$

Your task is to compute the total number of such palindromic subsequences.

inputFormat

The input consists of a single line containing the string s. The string only contains lowercase English letters.

outputFormat

Output a single integer: the number of palindromic subsequences of length 3 in the string s.

abcba

4