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

using vi = vector<int>;
#define sz(x) int(x.size())
#define rep(i, a, b) for(int i = (a); i < (b); i++)
array<vi, 2> manacher(const string& s) {
    int n = sz(s);
    array<vi,2> p = {vi(n+1), vi(n)};
    rep(z,0,2) for (int i=0,l=0,r=0; i < n; i++) {
        int t = r-i+!z;
        if (i < r) p[z][i] = min(t, p[z][l+t]);
        int L = i-p[z][i], R = i+p[z][i]-!z;
        while(L >= 1 && R+1 < n && s[L-1] == s[R+1])
            p[z][i]++, L--, R++;
        if(R>r) l=L, r=R;
    }
    return p;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const uint64_t B = 30 + rng() % 30, mod = 1e18 + 3;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    // string s = "aaaba";
    // auto [x, y] = manacher(s);
    // for(auto i : x) cout << i << " "; cout << endl;
    // for(auto i : y) cout << i << " "; cout << endl;

    int n;
    string s;
    cin >> n >> s;
    s += s;

    vector<uint64_t> H { 0 }, pws {1};
    for(int i = 0; i < s.size(); i++) {
        pws.push_back(pws.back() * __int128(1) * B % mod);
        H.push_back((H.back() + pws[i] * __int128(1) * (s[i] - '0' + 1)) % mod);
    }
    auto get = [&](int l, int r) -> uint64_t {//[l; r)
        if(l >= r) return 0;
        uint64_t s = mod + H[r] - H[l];
        s = s * __int128(1) * pws[sz(pws) - 1 - l] % mod;
        return s;
    };


    map<uint64_t, int> hash_to_id;
    vector<vector<int>> g(2 * n + 2);
    auto add = [&](int l, int r) -> void {
        int ch = -1;
        while(true) {
            int sz = hash_to_id.size();
            uint64_t ha = get(l, r);
            if(!hash_to_id.count(ha))
                hash_to_id[ha] = sz;
            if(ch != -1)
                g[hash_to_id[ha]].push_back(ch);
            ch = hash_to_id[ha];
            // cout << l << " " << r << " == " << ch << endl;
            if(ch != sz) break;
            l++, r--;
        }
    };

    int ans = 0;
    auto P = manacher(s);
    for(int z = 0; z < 2; z++) {
        g = vector<vector<int>>(2*n + 2);
        hash_to_id.clear();
        hash_to_id[0] = 0;
        vector<int> cnt(2*n + 2);

        for(int c = 0; c < 2 * n; c++ ) {
            int l = c - P[z][c], r = c + P[z][c] + z;
            int len = r - l;
            if(len > n) {
                int ex = (len - n + 1) / 2;
                l += ex, r -= ex;
            }
            add(l, r);
            // cout <<  c << " : " << l << " " << r << endl;
            cnt[hash_to_id[get(l, r)]]++;
            if(c < n) {//subtract duplicates
                if(r >= n) {
                    l += r - n;
                    r = n;
                }
                // cout << hash_to_id[get(l, r)] << " -: " << l << " " << r << endl;
                cnt[hash_to_id[get(l, r)]]--;
            }
        }
        
        auto dfs = [&](auto self, int v, int len) -> void {
            for(auto i : g[v]) {
                self(self, i, len + 2);
                cnt[v] += cnt[i];
            }
            // cout << v << " " << len << " " << cnt[v] << endl;
            if(len >= 1) {
                ans = (ans + (cnt[v]*1ll*cnt[v]%mod)*len)%mod;
            }
        };
        dfs(dfs, 0, -z);
    }
    cout << ans << '\n';
}