1923 - 子串sub
Description

给你一个由小写英文字母组成的字符串 SS 有多少个不同的非空子串?

子串是连续的子序列。例如,`xxx`是`yxxxy`的子串,但不是`xxyxx`的子串。


Input

一个字符串S

Output

输出答案

Examples

Input

yay

Output

5

Input

aababc

Output

17

Input

abracadabra

Output

54
Hint

- S 是长度在 1100 之间(含)的字符串,由小写英文字母组成。

样例1解释:

5

S 有以下五个不同的非空子串:

- `a`

- `y`

- `ay`

- `ya`

- `yay`


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1