#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long x = 0, F = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') F = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = (x << 3) + (x << 1) + c - '0';
    c = getchar();
  }
  return x * F;
}
int add(int a, int b) { return (a + b >= 51123987) ? a + b - 51123987 : a + b; }
int dec(int a, int b) { return (a - b < 0) ? a - b + 51123987 : a - b; }
int mul(long long a, int b) { return 1LL * a * b % 51123987; }
int ans, Tk, n, L[2000000 + 5], R[2000000 + 5], ecnt, head[2000000 + 5];
char s[2000000 + 5];
struct edge {
  int to, nxt, c;
} e[2000000 + 5];
void add(int u, int v, int c) {
  e[++ecnt] = (edge){v, head[u], c};
  head[u] = ecnt;
}
struct Palindromic_Tree {
  int dep[2000000 + 5], fa[2000000 + 5], len[2000000 + 5];
  int lst, tot;
  void init() {
    memset(head, 0, sizeof(head));
    ecnt = 0;
    memset(fa, 0, sizeof(fa)), memset(len, 0, sizeof(len)),
        memset(dep, 0, sizeof(dep));
    tot = 0, lst = 0;
    len[++tot] = -1;
    fa[0] = fa[1] = 1;
  }
  int get_id(int x, int c) {
    for (int i = head[x]; i; i = e[i].nxt)
      if (e[i].c == c) return e[i].to;
    return 0;
  }
  void Insert(int c, int L) {
    int p = lst;
    while (s[L - len[p] - 1] != s[L]) p = fa[p];
    if (!get_id(p, c)) {
      int np = ++tot, k = fa[p];
      len[np] = len[p] + 2;
      while (s[L - len[k] - 1] != s[L]) k = fa[k];
      fa[np] = get_id(k, c);
      dep[np] = dep[fa[np]] + 1;
      add(p, np, c);
    }
    lst = get_id(p, c);
  }
} T;
int main() {
  n = read();
  scanf("%s", s + 1);
  T.init();
  for (int i = 1; i <= n; i++) {
    T.Insert(s[i] - 'a', i);
    L[i] = T.dep[T.lst];
    ans = add(ans, L[i]);
  }
  ans = mul(1LL * ans * (ans - 1) / 2, 1);
  T.init();
  reverse(s + 1, s + n + 1);
  for (int i = n; i >= 1; i--) {
    T.Insert(s[n - i + 1] - 'a', n - i + 1);
    R[i] = T.dep[T.lst];
    R[i] = add(R[i], R[i + 1]);
  }
  for (int i = 1; i < n; i++) ans = dec(ans, mul(L[i], R[i + 1]));
  printf("%d\n", ans);
}
