白云有一个大小为$n$的串。

对于一个串$S$，白兔令这个串的最简表示为$(S',k)$。其中$S=S'^k$（即$S$为$k$个$S'$的连接）。在满足要求的情况下，最简表示会取$S'$最短的串。

白兔想从白云的串中选出两个不相交子串，它想知道，有多少种选取方式使得这两个子串的$k$值相同呢？

输入格式

一行一个小写字母字符串。

输出格式

输出方案数。

样例一

input

aaaa

output

7

样例二

input

abcd

output

15

限制与约定

对于30%的数据，$n \le 100$。

对于60%的数据，$n \le 2000$。

对于100%的数据，$n \le 10^5$

时间限制：1s

空间限制：512MB