You have a string A=A1 A2...An consisting of lowercase English letters.
You can choose any two indices i and j such that 1≤ i ≤ j ≤ n and reverse substring AiAi+1...Aj.
You can perform this operation at most once.
How many different strings can you obtain?
Constraints
1 ≤ |A| ≤ 200,000
A consists of lowercase English letters.
Input
String A
Output
Print the number of different strings you can obtain by reversing any substring in A at most once.
You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).