Count Strings

0

0 votes
Problem

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.

 

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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]).

Editor Image

?