#include <bits/stdc++.h>
using namespace std;
const int N = 26;
const int MAXN = 2e6 + 20;
const int mod = 51123987;
struct Palindromic_Tree {
  vector<pair<int, int> > next[MAXN];
  int fail[MAXN], len[MAXN], S[MAXN], num[MAXN];
  int last, n, p;
  int newnode(int l) {
    next[p].clear();
    num[p] = 0;
    len[p] = l;
    return p++;
  }
  int find(int u, int c) {
    vector<pair<int, int> >& x = next[u];
    int sz = x.size();
    for (int i = 0; i < sz; ++i) {
      if (x[i].first == c) return x[i].second;
    }
    return 0;
  }
  void init() {
    last = n = p = 0;
    S[0] = -1;
    newnode(0);
    newnode(-1);
    fail[0] = 1;
    fail[1] = 0;
  }
  int get_fail(int x) {
    while (S[n - len[x] - 1] != S[n]) {
      x = fail[x];
    }
    return x;
  }
  int add(int c) {
    c -= 'a';
    S[++n] = c;
    int cur = get_fail(last);
    int x = find(cur, c);
    if (x == 0) {
      int now = newnode(len[cur] + 2);
      x = now;
      fail[now] = find(get_fail(fail[cur]), c);
      next[cur].push_back(make_pair(c, now));
      num[now] = num[fail[now]] + 1;
    }
    last = x;
    return num[last];
  }
};
Palindromic_Tree T;
char s[MAXN];
long long L[MAXN], R[MAXN];
int main() {
  int n;
  while (scanf("%d%s", &n, s + 1) == 2) {
    memset(L, 0, sizeof(*L) * (n + 10));
    memset(R, 0, sizeof(*R) * (n + 10));
    T.init();
    for (int i = 1; i <= n; ++i) {
      R[i] = T.add(s[i]);
    }
    T.init();
    for (int i = n; i >= 1; --i) {
      L[i] = T.add(s[i]);
    }
    for (int i = n - 1; i >= 1; --i) L[i] = (L[i] + L[i + 1]) % mod;
    long long tot = L[1];
    tot %= mod;
    long long ans = tot * (tot - 1) / 2;
    for (int i = 1; i <= n; ++i) {
      ans = (ans + mod - (R[i] * L[i + 1] % mod)) % mod;
    }
    cout << ans << endl;
  }
  return 0;
}
