B - Reverse and Compare

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500

問題文

英小文字からなる文字列 A = A_1 A_2 ... A_n があります。

あなたは 1 \leq i \leq j \leq n であるような任意の二つの添字 i, j を選び、A のうち部分文字列 A_i A_{i+1} ... A_j を反転することができます。

この操作は一回まで行うことができます。

これによって得られる文字列は何通りあるでしょうか?

制約

  • 1 \leq |A| \leq 200,000
  • A は英小文字からなる。

入力

入力は以下の形式で標準入力から与えられる。

A

出力

A のうち任意の部分文字列を一回まで反転することによって、何通りの文字列が得られるか出力せよ。


入力例 1

aatt

出力例 1

5

得られる文字列は aatt(何もしない)、atatA[2..3] を反転)、attaA[2..4] を反転)、ttaaA[1..4] を反転)、taatA[1..3] を反転)です。


入力例 2

xxxxxxxxxx

出力例 2

1

どの部分文字列を反転しても、結果は xxxxxxxxxx です。


入力例 3

abracadabra

出力例 3

44

Score : 500 points

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 \leq i \leq j \leq 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?

Constraints

  • 1 \leq |A| \leq 200,000
  • A consists of lowercase English letters.

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.


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