Пароли

시간 제한2초메모리 제한1024 MB

요약

문자열 s를 세 부분 a, b, c로 나눌 때 a+b, b+c, a+c가 모두 서로 다른 분할의 수를 센다.

난이도: 보통10점 중 6점
유형: 문자열, 문자열 매칭, 해시맵
정답자: 아직 제출이 없습니다

문제

Ральф хочет зарегистрироваться на трех сайтах. Для каждого сайта Ральф хочет выбрать свой пароль, причем все три пароля должны быть различны. У Ральфа есть любимая строка $s$ . Для удобства запоминания паролей, Ральф решил разбить $s$ на три части: $a$ , $b$ и $c$ . Будем обозначать последовательное записывание двух строк операцией $+$ . Тогда $s = a + b + c$ . В качестве паролей Ральф будет использовать $a + b$ , $b + c$ и $a + c$ .

Помогите Ральфу посчитать количество различных способов разбить строку $s$ на $a$ , $b$ и $c$ , чтобы получившиеся пароли были различные. Два способа являются разными, если в них отличается хотя бы одна из строк $a$ , $b$ или $c$ .

입력

В единственной строке дана строка $s$ , состоящая из строчных латинских букв ( $1 \le |s| \le 500\\,000$ ).

출력

В единственной строке выведите одно целое число --- искомое количество разбиений.

예제2

예제 1
입력
```
aabc
```
예상 출력
```
2
```
예제 2
입력
```
ababcb
```
예상 출력
```
9
```