#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char c = getchar();
  int x = 0, f = 1;
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
  return x * f;
}
const int MAXN = 2e6 + 5;
const int Mod = 51123987;
const int Inv2 = (Mod + 1) / 2;
int N;
int f[MAXN], g[MAXN];
char s[MAXN];
inline void Add(int &x, int y) { x = (x + y) % Mod; }
inline int Sub(int x, int y) { return ((x - y) % Mod + Mod) % Mod; }
struct PAM {
  vector<pair<int, int>> G[MAXN];
  int fa[MAXN], dep[MAXN], cnt[MAXN], rec[MAXN];
  int lst, tot;
  char S[MAXN];
  inline int NewNode(int d) {
    dep[tot] = d;
    fa[tot] = 0;
    G[tot].clear();
    return tot++;
  }
  inline void Init() {
    tot = 0;
    lst = NewNode(-1);
    lst = NewNode(0);
  }
  inline int Son(int x, int c) {
    for (auto p : G[x])
      if (p.first == c) return p.second;
    return 0;
  }
  inline void Extend(int c, int pos) {
    int p = lst;
    while (S[pos - dep[p] - 1] != S[pos]) p = fa[p];
    if (!Son(p, c)) {
      int np = NewNode(dep[p] + 2), q = fa[p];
      while (S[pos - dep[q] - 1] != S[pos]) q = fa[q];
      fa[np] = Son(q, c);
      if (!fa[np]) fa[np] = 1;
      G[p].push_back({c, np});
    }
    lst = Son(p, c);
    rec[pos] = cnt[lst] = cnt[fa[lst]] + 1;
  }
  inline void solve(int op) {
    for (int i = 1; i <= N; i++) S[i] = s[i];
    if (op == 1) reverse(S + 1, S + N + 1);
    Init();
    for (int i = 1; i <= N; i++) Extend(S[i] - 'a', i);
    if (!op)
      memcpy(f, rec, sizeof(f));
    else
      memcpy(g, rec, sizeof(g));
  }
} pam;
int main() {
  N = read();
  scanf("%s", s + 1);
  pam.solve(0);
  pam.solve(1);
  reverse(g + 1, g + N + 1);
  int cntf = 0, cntg = 0, ans = 0, all = 0;
  for (int i = 1; i <= N; i++) {
    Add(cntf, f[i]);
    Add(cntg, g[i]);
  }
  for (int i = N; i; i--) Add(g[i], g[i + 1]);
  for (int i = 1; i <= N; i++) Add(ans, (long long)f[i] * g[i + 1] % Mod);
  all = (long long)cntf * cntg % Mod;
  all = Sub(all, g[1]);
  all = (long long)all * Inv2 % Mod;
  printf("%d\n", Sub(all, ans));
  return 0;
}
