#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int P1 = 972152273, base1 = 809;
const int P2 = 905563261, base2 = 919;
const int N = 1000005;
int fact1[N], fact2[N];
int L = 2000000;
vector<int> pre1(L + 2), pre2(L + 2);
pii getHash (int l, int r) {
    pii ans = {0, 0};
    if (l > r) return ans;
    ans.first  = ((pre1[r] - pre1[l - 1] * fact1[r - l + 1] % P1) + P1) % P1;
    ans.second = ((pre2[r] - pre2[l - 1] * fact2[r - l + 1] % P2) + P2) % P2;
    return ans;
}
signed main()
{
    int n;
    cin>>n;
    string s;
    cin>>s;
    fact1[0] = fact2[0] = 1;
    for (int i = 1; i < N; i++) {
        fact1[i] = fact1[i - 1] * base1 % P1;
        fact2[i] = fact2[i - 1] * base2 % P2;
    }
    s = ' ' + s;
    L=s.size();
    for (int i = 1; i <= L; i++) {
        pre1[i] = ( pre1[i - 1] * base1 + s[i]) % P1;
        pre2[i] = ( pre2[i - 1] * base2 + s[i]) % P2;
    }
}