#include <bits/stdc++.h>
using namespace std;
const int N = 2000005, mod = 51123987;
char s[N];
int n, len[N], pre[N], lst, tot, head[N], cnt, dep[N], ans, pl[N], pr[N];
struct Edge {
  int v, w, next;
} e[N];
void init() {
  pre[lst = 0] = pre[1] = 1;
  len[tot = 1] = -1;
  memset(head, 0, sizeof(head));
  cnt = 0;
}
void adde(int u, int v, int w) {
  e[++cnt] = (Edge){v, w, head[u]};
  head[u] = cnt;
}
int ch(int u, int alp) {
  for (int i = head[u]; i; i = e[i].next)
    if (e[i].w == alp) return e[i].v;
  return 0;
}
void insert(int alp, int n) {
  int p = lst, k;
  while (s[n - len[p] - 1] != s[n]) p = pre[p];
  if (!ch(p, alp)) {
    len[++tot] = len[p] + 2;
    k = pre[p];
    while (s[n - len[k] - 1] != s[n]) k = pre[k];
    pre[tot] = ch(k, alp);
    adde(p, tot, alp);
    dep[tot] = dep[pre[tot]] + 1;
  }
  lst = ch(p, alp);
}
int main() {
  scanf("%d%s", &n, s + 1);
  init();
  for (int i = 1; i <= n; i++) {
    insert(s[i] - 'a', i);
    (ans += pl[i] = dep[lst]) %= mod;
  }
  ans = 1LL * ans * (ans - 1) / 2 % mod;
  reverse(s + 1, s + 1 + n);
  init();
  for (int i = 1; i <= n; i++) {
    insert(s[i] - 'a', i);
    pr[n - i + 1] = dep[lst];
  }
  for (int i = n; i >= 1; i--) (pr[i] += pr[i + 1]) %= mod;
  for (int i = 1; i < n; i++) {
    (ans += mod - 1LL * pl[i] * pr[i + 1] % mod) %= mod;
  }
  printf("%d\n", ans);
  return 0;
}
