Count New Strings

题号：NC209485
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Besides data structures and number theory, ZYB also loves strings.

Consider a string ${S}$ of length ${n}$ , denote $S_i$ as the ${i}$ -th character in the string (1-based).

Define a string function $f(S, x, y)(1 \leq x \leq y \leq n)$ such that ${|f(S, x, y)|=y-x+1}$ and the ${k}$ -th character of ${f(S, x, y)}$ is $\max_{i=x \dots x+k-1} S_i$ .

For example, if ${S=dbca}$ , then ${f(S, 1, 4)} = dddd, f(S, 2, 4) = bcc$ .
Let ${A=\{f(f(S,x_1,y_1), x_2-x_1+1,y_2-x_1+1) \mid 1 \leq x_1 \leq x_2 \leq y_2 \leq y_1 \leq n\}}$ . ZYB wants to know how many different strings in set ${A}$ (i.e. the value of ${|A|}$ ).

输入描述:

The input only contains one test case. 
There is a string  in the first line, indicating the string we focus. 
It is guaranteed that the string is composed of only first  lowercase letters (i.e. ).

输出描述:

The output only contains one integer indicating the answer.

示例1

输入

复制

dbca

输出

复制

示例2

输入

复制

dbcad

输出

复制