#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define Mp make_pair
#define SZ(x) (int((x).size()))

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

constexpr int P1 = 998244353, P2 = 1e9 + 7, b1 = 231, b2 = 13131, N = 20000100;
pii pw[N]; multiset<pii> st[2000100];

void solve() {
    int n; string s;
    cin >> n >> s;
    s = ' ' + s + s + s;
    
    pw[0] = Mp(1, 1);
    for(int i = 1; i < N; i++) {
        pw[i] = Mp( 1ll * pw[i - 1].fi * b1 % P1,
                    1ll * pw[i - 1].se * b2 % P2);
    }
    vector<pii> hsh; hsh.pb(Mp(0, 0));
    auto push = [&](vector<pii> &h, char ch) {
        auto [a, b] = h.back();
        hsh.pb(Mp(  (1ll * a * b1 + ch) % P1,
                    (1ll * b * b2 + ch) % P2));
    };
    auto get = [&](vector<pii> &h, int l, int r) -> pii {
        auto L = h[l - 1], R = h[r];
        int len = r - l + 1;
        return Mp(  (R.fi - 1ll * L.fi * pw[len].fi % P1 + P1) % P1,
                    (R.se - 1ll * L.se * pw[len].se % P2 + P2) % P2);
    };

    string t = "-$";
    for(int i = 1; i <= 3 * n; i++) {
        t += s[i];
        t += '#';
    }
    t.pop_back(), t += "@";
    for(int i = 1; i < SZ(t); i++) {
        push(hsh, t[i]);
    }

    // cout << "f" << endl;
    vi r(4 * n + 2), fr(4 * n + 2), frlen(4 * n + 2);
    for(int i = 1, rmx = 0, center = 0; i <= 4 * n; i++) {
        if(i <= rmx) {
            r[i] = min(r[2 * center - i], rmx - i + 1);
            if(2 * center - i >= 2 * n + 1)
                fr[i] = 2 * center - i, frlen[i] = r[i];
        }
        while(i - r[i] > 0 && i + r[i] < SZ(t) && t[i - r[i]] == t[i + r[i]]) r[i]++;
        if(i + r[i] - 1 > rmx) rmx = i + r[i] - 1, center = i;
    }
    // cout << "f" << endl;
    // for(int i = 2 * n + 1; i <= 4 * n; i++) {
    //     cout << fr[i] << ' ' << frlen[i] << endl;
    // }
// t = -$0#1#0#1#0#_0#1#0#1#0_20_#0#1#0#1#0@
    vi cnt(4 * n + 2);
    map<pair<pii, int>, int> mp;
    for(int i = 4 * n; i >= 2 * n + 1; i--) {
        cnt[i]++;
        if(i & 1) { // even length
            while(r[i] > frlen[i]) {
                while(SZ(st[i]) && -st[i].begin()->fi == r[i]) {
                    cnt[i] += st[i].begin()->se;
                    st[i].erase(st[i].begin());
                }
                if(r[i] % 2 == 0 && r[i] <= n) {
                    auto h = get(hsh, i - r[i] + 1, i + r[i] - 1);
                    mp[Mp(h, r[i])] += cnt[i];
                    // cout << i - r[i] + 1 << ' ' << i + r[i] - 1 << ' ' << r[i] << ' ' << cnt[i] << "    " << h.fi << ' ' << h.se << endl;
                }
                r[i]--;
            }
        } else {
            while(r[i] > frlen[i]) {
                while(SZ(st[i]) && -st[i].begin()->fi == r[i]) {
                    cnt[i] += st[i].begin()->se;
                    st[i].erase(st[i].begin());
                }
                if(r[i] % 2 != 0 && r[i] <= n) {
                    auto h = get(hsh, i - r[i] + 1, i + r[i] - 1);
                    // cout << i - r[i] + 1 << ' ' << i + r[i] - 1 << ' ' << r[i] << ' ' << cnt[i] << "    " << h.fi << ' ' << h.se << endl;
                    mp[Mp(h, r[i])] += cnt[i];
                }
                r[i]--;
            }
        }
        auto merge = [&](multiset<pii> &st1, multiset<pii> &st2) {
            if(SZ(st1) < SZ(st2)) swap(st1, st2);
            for(auto o : st2) st1.insert(o);
        };
        if(fr[i]) {
            // assert(0 <= fr[i] - 2 * n && fr[i] - 2 * n < 2000100);
            // assert(0 <= i - 2 * n && i - 2 * n < 2000100);
            merge(st[fr[i] - 2 * n], st[i - 2 * n]);
            st[fr[i] - 2 * n].insert(Mp(-frlen[i], cnt[i]));
        }
    }
    // cout << "f" << endl;

    ll ans = 0;
    for(auto [p, c] : mp) {
        int len = p.se;
        // cout << len << ' ' << c << '\n';
        ans += 1ll * c * c * len;
    }

    cout << ans << '\n';
}
signed main() {
    // freopen("data.in", "r", stdin);
    atexit([]{cerr << 1. * clock() / CLOCKS_PER_SEC << "s\n";});
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}