### Суффиксный массив без векторов

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long ll
#define all(x) begin(x), end(x)
#define array array_

const int N = 3e6;

int n;
char s[N];
int equiv[N];
int temp[N];
int array[N];
int bucket_size[N];


void build() {
    for (int i = 0; i < n; ++i) {
        equiv[i] = s[i] + 1;
        ++bucket_size[equiv[i]];
    }
    int mb = 256;
    for (int i = 1; i <= mb; ++i) {
        bucket_size[i] += bucket_size[i - 1];
    }
    for (int i = 0; i < n; ++i) {
        assert(array[bucket_size[equiv[i] - 1]] == 0);
        array[bucket_size[equiv[i] - 1]++] = i;
    }
    fill_n(bucket_size, mb + 1, 0);

    for (int l = 1; l < n; l *= 2) {
        for (int i = 0; i < n; ++i) {
            ++bucket_size[equiv[i]];
        }
        mb = *max_element(equiv, equiv + n);

        for (int i = 1; i <= mb; ++i) {
            bucket_size[i] += bucket_size[i - 1];
        }
        for (int i = 0; i < n; ++i) {
            int first = array[i] - l;
            if (first < 0) {
                first += n;
            }
            temp[bucket_size[equiv[first] - 1]++] = first;
        }
        copy_n(temp, n, array);
        fill_n(bucket_size, mb + 1, 0);

        temp[array[0]] = 1;
        for (int a, b, c, d, i = 1; i < n; ++i) {
            a = array[i];
            b = array[i - 1];
            c = a + l;
            d = b + l;
            if (c >= n) {
                c -= n;
            }
            if (d >= n) {
                d -= n;
            }
            temp[a] = temp[b];
            if ((equiv[a] > equiv[b]) || (equiv[c] > equiv[d])) {
                ++temp[a];
            }
        }
        copy_n(temp, n, equiv);
    }
}

int main() {
    assert(freopen("input.txt", "r", stdin));
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    n = (int)strlen(s);
    s[n++] = '#';

    build();

    uint64_t h = 0;
    for (int i = 1; i < n; ++i) {
        h *= 3;
        h += array[i];
    }

    cout << h << '\n';
    cout << 1000 * clock() / CLOCKS_PER_SEC << '\n';
    return 0;
}