Vasya 在 Yandex 工作时正在开会。突然，他想到了一个由小写英文字母组成的字符串 $s$。

然后他定义，如果一个字符串 $t = t_1t_2 \dots t_m$ ($m > 0$) 是 $s$ 的子串，且 $t$ 的左循环移位 $t' = t_2 \dots t_mt_1$ 也是 $s$ 的子串，那么称 $t$ 为关于 $s$ 的“好字符串”。

Vasya 本打算计算关于给定字符串 $s$ 的不同好字符串 $t$ 的数量……但突然一位同事问了他一个问题，他不得不回到现实。请在他忙于会议时帮他算出这个数量。

输入格式

输入仅一行，包含一个由 $n$ ($1 \le n \le 300\,000$) 个小写英文字母组成的字符串 $s$。

输出格式

输出一个整数：关于给定字符串 $s$ 的不同好字符串 $t$ 的数量。

样例

样例输入 1

abaac

样例输出 1

7

样例输入 2

aaa

样例输出 2

3

说明

在第一个样例中，好字符串恰好是以下字符串：a, b, c, aa, ab, ba, aba。

在第二个样例中，好字符串恰好是以下字符串：a, aa, aaa。