Problem Statement
You have a string A = A_1 A_2 ... A_n consisting of lowercase English letters.
You can choose any two indices i and j such that 1 ≤ i ≤ j ≤ n and reverse substring A_i A_{i+1} ... A_j.
You can perform this operation at most once.
How many different strings can you obtain?
Input
Input is given from Standard Input in the following format:
A
Output
Print the number of different strings you can obtain by reversing any substring in A at most once.
Limits
For all subtasks: 1 ≤ |A| ≤ 200,000. A consists of lowercase English letters.
Subtask 1 (11%): 1 ≤ |A| ≤ 100
Subtask 2 (48%): 1 ≤ |A| ≤ 2000
Subtask 3 (41%): No additional contraints
Subtask 4 (0%): Sample Testcases
Sample Input 1
aatt
Sample Output 1
5
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]).
Sample Input 2
xxxxxxxxxx
Sample Output 2
1
Whatever substring you reverse, you'll always get xxxxxxxxxx.
Sample Input 3
abracadabra
Sample Output 3
44