#include <bits/stdc++.h>
template <typename T>
inline void read(T &x) {
  x = 0;
  char c = getchar();
  bool flag = false;
  while (!isdigit(c)) {
    if (c == '-') flag = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c ^ 48);
    c = getchar();
  }
  if (flag) x = -x;
}
using namespace std;
const int P = 51123987;
int n;
char s[2001000];
struct PAM {
  struct edge {
    int nxt, to, c;
  } e[2001000];
  int head[2001000], ecnt;
  inline void addedge(int from, int to, int c) {
    e[++ecnt] = (edge){head[from], to, c};
    head[from] = ecnt;
  }
  inline int son(int cur, int c) {
    for (register int i = head[cur]; i; i = e[i].nxt)
      if (e[i].c == c) return e[i].to;
    return 0;
  }
  int len[2001000], fail[2001000], dep[2001000], lst, tot;
  inline void init() {
    memset(head, 0, sizeof(head));
    memset(len, 0, sizeof(len));
    memset(dep, 0, sizeof(dep));
    memset(fail, 0, sizeof(fail));
    lst = ecnt = 0;
    len[1] = -1;
    fail[0] = fail[1] = 1;
    tot = 1;
  }
  inline int ins(int pos) {
    int p = lst, c = s[pos] - 'a';
    while (s[pos - len[p] - 1] != s[pos]) p = fail[p];
    if (son(p, c)) return dep[lst = son(p, c)];
    int x = fail[p];
    while (s[pos - len[x] - 1] != s[pos]) x = fail[x];
    int np = ++tot;
    fail[np] = son(x, c);
    dep[np] = dep[fail[np]] + 1;
    addedge(p, np, c);
    len[np] = len[p] + 2;
    return dep[lst = np];
  }
} pam;
long long cnt[2001000];
int main() {
  read(n);
  scanf("%s", s + 1);
  pam.init();
  long long stot = 0;
  for (register int i = 1; i <= n; ++i)
    cnt[i] = pam.ins(i), stot += cnt[i], cnt[i] = (cnt[i] + cnt[i - 1]) % P;
  for (register int i = 1; i < (n - i + 1); ++i)
    swap(cnt[i], cnt[n - i + 1]), swap(s[i], s[n - i + 1]);
  pam.init();
  long long ans = 0;
  for (register int i = 1; i <= n; ++i) {
    int tmp = pam.ins(i);
    ans = (ans + cnt[i + 1] * tmp) % P;
  }
  if (stot & 1)
    ans = ((stot - 1) >> 1) % P * (stot % P) % P - ans;
  else
    ans = (stot >> 1) % P * ((stot - 1) % P) % P - ans;
  printf("%lld\n", (ans % P + P) % P);
  return 0;
}
