시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

Prefikso-sufiksem danego słowa w nazywamy słowo v, które jest zarówno prefiksem (początkowym fragmentem), jak i sufiksem (końcowym fragmentem) w. Prefikso-sufiksem właściwym w jest każdy jego prefikso-sufiks, który jest niepusty i krótszy od w. Niech PS(w) oznacza liczbę właściwych prefikso-sufiksów słowa w. Przez w[i, j] oznaczamy podsłowo słowa w zaczynające się na pozycji i i kończące się na pozycji j. Pozycje numerujemy od 1.

Dane jest słowo w. Twoim zadaniem jest wyznaczenie łącznej liczby właściwych prefikso-sufiksów wszystkich podsłów w, czyli obliczenie wyrażenia

\[\sum_{1 \le i \le j \le \left|w\right|}{PS\left(w\left[i, j\right]\right)}\text{.}\]

입력

W pierwszym i jedynym wierszu wejścia znajduje się słowo w, składające się z co najmniej 1 i co najwyżej 105 znaków. W słowie występują jedynie małe litery alfabetu angielskiego.

출력

Na wyjściu należy wypisać sumaryczną liczbę właściwych prefikso-sufiksów wszystkich podsłów w.

예제 입력 1

ababa

예제 출력 1

7