蒜斜刚来PKU的时候还不知道有“北大算协”这个社团，因此他总是觉得周围的人在偷偷议论着他，比如说：

“算协（注：非蒜斜）举办的活动好有趣啊！”

“算协（注：非蒜斜）好帅啊！”

蒜斜每次听到这些话就会想入非非，但仔细想想，自己好像也没有那么帅吧？最离谱的一次还是：

“算协（注：非蒜斜）有好多小哥哥”（雾）

自从蒜斜学习了半前缀之后，他把这些话都看开了 —— 对他来说，只要这些话里有 “蒜斜好” 的半前缀就足够了。

题目描述

设小写字母字符串 $s$, 长度为 $n$, $s[l:r]$ 表示第 $l$ 个到第 $r$ 个字符构成的子串, $l>r$ 时对应空串。

定义半前缀是 $s[1:i]+s[j:k]$, 其中 $0\le i<len(s),i<j\le len(s),j-1\le k\le len(s)$。直观上来说，你可以把半前缀理解成某一个前缀 $s[1:k]$ 删除掉某一个子串后形成的结果（当然也允许不删）。

给出字符串 $s$，你需要求出 $s$ 的所有半前缀中，有多少个不同的字符串。

输入格式

输入一行包含一个小写字符串 $s(1\le |s|\le {10}^6)$。

输出格式

输出一行一个整数，表示答案。

样例一

input

aab

output

6

explanation

字符串 aab 的半前缀有：空串，a，b，aa，ab，aab。

样例二

input

pkusaamtcup

output

217

限制与约定

Small Task: $|s|\le 3000$。

Large Task: $|s|\le {10}^6$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载