#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2000005;
const int MOD = 51123987;
int n, ans[MAXN], pre[MAXN], ANS, ansp[MAXN];
long long S;
int Read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c > '9' || c < '0') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x * 10) + (c ^ 48);
    c = getchar();
  }
  return x * f;
}
void Put1(int x) {
  if (x > 9) Put1(x / 10);
  putchar(x % 10 ^ 48);
}
void Put(int x, char c = -1) {
  if (x < 0) putchar('-'), x = -x;
  Put1(x);
  if (c >= 0) putchar(c);
}
template <typename T>
T Max(T x, T y) {
  return x > y ? x : y;
}
template <typename T>
T Min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T Abs(T x) {
  return x < 0 ? -x : x;
}
struct PAM {
  int head[MAXN], etot;
  struct edge {
    int v, w, nxt;
  } e[MAXN];
  void Add_Edge(int x, int y, int z) {
    e[++etot].v = y;
    e[etot].w = z;
    e[etot].nxt = head[x];
    head[x] = etot;
  }
  int check(int x, int y) {
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].w == y) return e[i].v;
    return 0;
  }
  char s[MAXN];
  int tot, lst;
  struct node {
    int d, len, fail;
  } t[MAXN];
  PAM() {
    t[0].fail = 1;
    t[1].fail = 1;
    t[0].len = 0;
    t[1].len = -1;
    lst = 0;
    tot = 1;
  }
  void clr() {
    for (int i = 2; i <= tot; ++i) t[i].fail = t[i].d = t[i].len = 0;
    for (int i = 0; i <= tot; ++i) head[i] = 0;
    lst = etot = 0;
    tot = 1;
  }
  int gf(int x, int now) {
    while (s[now - t[x].len - 1] != s[now]) x = t[x].fail;
    return x;
  }
  void ins(int now, int c) {
    int p = gf(lst, now);
    if (!check(p, c)) {
      t[++tot].len = t[p].len + 2;
      t[tot].fail = check(gf(t[p].fail, now), c);
      t[tot].d = t[t[tot].fail].d + 1;
      Add_Edge(p, tot, c);
    }
    lst = check(p, c);
    S += ans[now] = t[lst].d;
  }
} P;
int main() {
  n = Read();
  scanf("%s", P.s + 1);
  for (int i = 1; i <= n; ++i) P.ins(i, P.s[i] - 'a');
  if (S & 1)
    ANS = S % MOD * ((S - 1) / 2 % MOD) % MOD;
  else
    ANS = S / 2 % MOD * ((S - 1) % MOD) % MOD;
  for (int i = 1; i <= n; ++i) ansp[i] = ans[i];
  for (int i = 1; i <= n / 2; ++i) swap(P.s[i], P.s[n - i + 1]);
  P.clr();
  for (int i = 1; i <= n; ++i) P.ins(i, P.s[i] - 'a');
  for (int i = 1; i <= n; ++i) pre[i] = (pre[i - 1] + ans[i]) % MOD;
  for (int i = 1; i <= n; ++i) ANS = (ANS - 1ll * ansp[i] * pre[n - i]) % MOD;
  Put((ANS + MOD) % MOD);
  return 0;
}
