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.</p>

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 10⁵ 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.

예제 입력

ababa

예제 출력

7