순환 이동

Vasya는 Yandex에서 근무하던 중 회의에 참석하고 있었다. 그러던 중 영소문자로 이루어진 문자열 $s$가 머리에 떠올랐다.

문자열 $t = t_1 t_2 \dots t_m$ ($m > 0$)이 $s$의 부분 문자열이고, $t$의 왼쪽 원형 이동 $t' = t_2 \dots t_m t_1$도 $s$의 부분 문자열이면, $t$를 $s$에 대한 좋은 문자열이라고 정했다.

Vasya는 $s$에 대한 서로 다른 좋은 문자열의 개수를 세려고 했지만, 동료의 질문을 받고 회의에 복귀해야 했다. 그를 대신해 그 개수를 구하시오.

첫 줄에 문자열 $s$가 주어진다. $s$의 길이 $n$은 $1 \leq n \leq 300000$을 만족한다. 문자열은 영소문자로만 이루어져 있다.

좋은 문자열 $t$의 서로 다른 개수를 한 개의 정수로 출력한다.

첫 번째 예제에서 좋은 문자열은 정확히 a, b, c, aa, ab, ba, aba이다.

두 번째 예제에서 좋은 문자열은 정확히 a, aa, aaa이다.