该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

在一个字符串中，假设有某一个字母只出现过一次，那么我们就称它为坏字符串。

例如 "abb","bcdde" 就是坏字符串，而 "aa","abcacb" 是好字符串。

给一个字符串，请问他有多少个子串是坏字符串。

Format

Input

输入一个字符串

Output

输出答案

Samples

abba

8

Limitation

对于20%的数据 字符串长度不超过200

对于另外20%的数据 字符串长度不超过2000

对于另外10%的数据 字符串长度不超过1e5且字符种类数不超过2

对于另外10%的数据 字符串长度不超过1e5

对于另外10%的数据 字符种类数不超过2

对于100%的数据 字符串长度不超过5e6