You are given a string S consisting of lowercase English letters.

Count the total number of palindromic subsequences of length exactly 3.

A subsequence is obtained by deleting zero or more characters without changing the order of the remaining characters.

A palindrome reads the same forwards and backwards.

Print the total count.

---

Input Format

• First line contains the string S.

---

Output Format

Print a single integer representing the number of palindromic subsequences of length 3.

---

Constraints

• (1 <= |S|<= 2 * 10^5)

---

Example 1

Input

abca

Output

2

---

Explanation

The valid palindromic subsequences are:

• aba
• aca

---

Example 2

Input

aaa

Output

1

---

Example 3

Input

aaaa

Output

4

---

Explanation

Choose any 3 of the 4 'a' characters:

[ \binom{4}{3}=4 ]

Hence the answer is 4.