Description

刘学习最近学习后缀数组，学不会，于是他干脆发明了一种数据结构叫做”前缀数组“。在学习这个数据结构之前，我们首先需要了解一下什么是前缀：对于一个字符串|S|，若S可以用字符数组表示成a[1],a[2]...a[n]他的第i个前缀指的是a[1]...a[i]这一段字符构成的串。例如S=‘abcde‘，则他有
a
ab
abc
abcd
abcde
五个不同的前缀
对于一个字符串S，学习的前缀数组Pa[]含义如下：
Pa[i]表示在S的所有前缀中，字典序第i大的前缀的最右边那个字符的下标。
现在给定字符串S，你需要想办法得到他的前缀数组。
为了让你快乐，你只需要输出Pa[]数组中（每个元素的值和他下标的乘积）的和。
即Pa[1]*1+Pa[2]*2+...+Pa[n]*n

Format

Input

一个字符串S
保证|S|<=100
且S中仅有小写英文字母

Output

一个正整数，即题目所求答案

Sample 1

Input

aa

Output

5

Limitation

1s, 64MB for each test case.

Source

2019网宿杯XMU程序设计竞赛网络预赛第一场