소문자로 이루어진 문자열 $s$가 주어진다. 이 문자열의 길이를 $|s|$, 뒤집은 문자열을 $s^R$라고 하자. 즉, $s^R$는 $s$를 좌우로 뒤집어 얻은 문자열이다. 또한 $\operatorname{prefix}(s, i)$는 $s$의 처음 $i$개 문자로 이루어진 부분 문자열, $\operatorname{suffix}(s, i)$는 $s$의 마지막 $i$개 문자로 이루어진 부분 문자열을 나타낸다.

이를 바탕으로 문자열 $s$의 $\operatorname{Porder}$ 값을 다음 조건을 만족하는 가장 큰 정수 $i$로 정의한다: $$\operatorname{prefix}(s, i) = (\operatorname{suffix}(s, i))^R$$ 여기서 $0 \le i \le |s|$이다. 특히 위 조건을 만족하는 양의 정수가 없다면 $\operatorname{Porder}$ 값은 $0$이다.

문자열 $s$의 부분 문자열은 $l$번째 문자부터 $r$번째 문자까지의 연속된 문자들의 나열로 정의된다. 인덱스는 $1$부터 시작하며 $1 \le l \le r \le |s|$를 만족한다.

문자열 $s$의 모든 부분 문자열의 $\operatorname{Porder}$ 값의 합을 구하여라.

입력

입력은 한 줄이며 문자열 $s$가 주어진다 $(1 \le |s| \le 10^5)$. 문자열이 소문자로만 이루어져 있음이 보장된다.

출력

$s$의 모든 부분 문자열의 $\operatorname{Porder}$ 값의 합을 나타내는 정수 하나를 한 줄에 출력하여라.

예제

입력 1

aa

출력 1

4

입력 2

abcdba

출력 2

9

참고

예제 2를 살펴보자:

• $\operatorname{Porder}$ 값이 $2$인 부분 문자열은 abcdba이다 (총 $1$개).

• $\operatorname{Porder}$ 값이 $1$인 부분 문자열은 bcdb와 길이가 $1$인 모든 부분 문자열이다 (총 $7$개).

• 나머지 부분 문자열의 $\operatorname{Porder}$ 값은 모두 $0$이다.

따라서 모든 부분 문자열의 $\operatorname{Porder}$ 값의 합은 $1 \times 2 + 7 \times 1 + 0 = 9$이다.