suff_array

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cassert>

using namespace std;

#define pb push_back
#define mp make_pair
#define sz(A) (int)(A).size()

typedef unsigned long long LL;
typedef long double LD;

const int N = 31715;
const LL P = LL(1e9 + 7);

LL hash[N], p[N];
char s[N];
LL res;
bool ok;
int len;

pair<LL, int> sf[N];

LL count_hash(int l, int r) {
    if (!l)
        return hash[r];
    else
        return hash[r] - hash[l - 1] * p[r - l + 1];
}

LL count_cycled(int l, int r) {
    if (l < r)
        return count_hash(l, r);
    LL h = count_hash(l, len - 1) * p[r] + count_hash(0, l - 1);
    return h;
}

bool comp (pair<LL, int> a, pair<LL, int> b) {
    int l = 0, r = len + 1;

    int p1 = a.second, p2 = b.second;

    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (count_cycled(p1, (p1 + mid - 1) % len) != count_cycled(p2, (p2 + mid - 1) % len))
            r = mid;
        else
            l = mid;
    }
//  cerr << (s[p1]) << " " << s[p2] << endl;
    cerr << l << endl;
    return (s[(p1 + l) % len] < s[(p2 + l) % len]);
}

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    gets(s);
    len = strlen(s);

    s[len++] = char('z' + 1);

    p[0] = 1;
    for (int i = 1; i <= len; i++)
        p[i] = p[i - 1] * P;

    hash[0] = s[0];
    for (int i = 1; i < len; i++)
        hash[i] = hash[i - 1] * P + s[i];

    for (int i = 0; i < len; i++) {
        LL h = (i == 0 ? count_hash(0, len - 1) : count_cycled(i, i - 1));
        sf[i] = mp(h, i);
    }

    sort(sf, sf + len, comp);

    int Len = len - sf[0].second - 1;
    res = Len * (Len + 1) / 2;

//  cerr << res << endl;

    for (int i = 1; i < len - 1; i++) {
        int p1 = sf[i].second, p2 = sf[i - 1].second;
        int l = 0, r = len + 1;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (count_cycled(p1, (p1 + mid - 1) % len) != count_cycled(p2, (p2 + mid - 1) % len))
                r = mid;
            else
                l = mid;
        }

        Len = len - sf[i].second - 1;
//      res += (Len + 1) * Len / 2 - (l * (l + 1)) / 2;
        res += (Len + l + 1) * (Len - l) / 2;
//      cerr << res << endl;

    }

    printf("%I64d\n", res);

    cerr << double(clock()) / CLOCKS_PER_SEC << endl;

    return 0;
}