给定字符串 S ，求出 S 的每个真前缀在 S 的出现次数。为了防止输出过长，设长为 i 的前缀出现次数为 t(i) ，你只需要输出 \sum_{i=1}^{|S|-1} i\times t(i) 即可
输入
输入一行一个由不含空格的可显示 ASCII 字符组成的字符串 S(2\le |S|\le 2\times 10^6)
输出
输出一行一个整数，代表 \sum_{i=1}^{|S|-1} i\times t(i)
样例
| 标准输入 复制文本 |
ababc |
| 标准输出 复制文本 |
13 |
| 标准输入 复制文本 |
abacaba |
| 标准输出 复制文本 |
29 |
| 标准输入 复制文本 |
lr580 |
| 标准输出 复制文本 |
10 |
提示
对 ababc ，有 t(1)=t(2)=2,t(3)=t(4)=1
对 abacaba ，有 t(1)=4,t(2)=t(3)=2,t(4)=t(5)=t(6)=1
对 lr580 ，有 t(1)=t(2)=t(3)=t(4)=1
保证输出结果不会大于 long long 所能表示的范围