#include <bits/stdc++.h>
using namespace std;
struct ins {
  int ans;
  ins() { ans = 1; }
  void read() {}
  void read1(char &s) {
    char c = getchar();
    for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
      ;
    s = c;
    if (c == EOF) ans = 0;
  }
  void read1(string &s) {
    s = "";
    char c = getchar();
    for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
      ;
    for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
      s += c;
    if (c == EOF) ans = 0;
  }
  void read1(char *s) {
    char c = getchar();
    int tt = 0;
    for (; !isprint(c) || c == ' ' || c == '\n' || c == '\t'; c = getchar())
      ;
    for (; isprint(c) && c != ' ' && c != '\n' && c != '\t'; c = getchar())
      s[tt++] = c;
    if (c == EOF) ans = 0;
  }
  template <typename T>
  void read1(T &n) {
    T first = 0;
    int f = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) {
      if (c == '-') f = -1;
      if (c == EOF) {
        ans = 0;
        return;
      }
    }
    for (; isdigit(c); c = getchar()) first = first * 10 + c - 48;
    n = first * f;
    if (c == EOF) ans = 0;
    if (c != '.') return;
    T l = 0.1;
    while ((c = getchar()) <= '9' && c >= '0')
      first = first + (c & 15) * l, l *= 0.1;
    n = first * f;
    if (c == EOF) ans = 0;
  }
  void write() {}
  void write1(string s) {
    int n = s.size();
    for (int i = 0; i < n; i++) putchar(s[i]);
  }
  void write1(const char *s) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) putchar(s[i]);
  }
  void write1(char *s) {
    int n = strlen(s);
    for (int i = 0; i < n; i++) putchar(s[i]);
  }
  void write1(char s) { putchar(s); }
  void write1(float s, int first = 6) {
    char second[10001];
    sprintf(second, "%%.%df", first);
    printf(second, s);
  }
  void write1(double s, int first = 6) {
    char second[10001];
    sprintf(second, "%%.%dlf", first);
    printf(second, s);
  }
  void write1(long double s, int first = 6) {
    char second[10001];
    sprintf(second, "%%.%dLf", first);
    printf(second, s);
  }
  template <typename T>
  void write1(T n) {
    if (n < 0) n = -n, putchar('-');
    if (n > 9) write1(n / 10);
    putchar('0' + n % 10);
  }
  friend ins operator>>(ins first, char *n);
  template <typename T>
  friend ins operator>>(ins first, T &n);
  template <typename T>
  friend ins operator<<(ins first, T n);
  operator bool() { return ans; }
};
ins operator>>(ins first, char *n) {
  if (!first.ans) return first;
  first.read1(n);
  return first;
}
template <typename T>
ins operator>>(ins first, T &n) {
  if (!first.ans) return first;
  first.read1(n);
  return first;
}
template <typename T>
ins operator<<(ins first, T n) {
  first.write1(n);
  return first;
}
ins yin;
ins yout;
using namespace std;
const long long maxn = 4e6 + 51, mod = 51123987, inv2 = 25561994;
long long n, mxr, mid, c, res, lx, rx;
long long rad[maxn], f[maxn], g[maxn];
char s[maxn], ch[maxn];
int main() {
  yin >> n >> (s + 1);
  ch[0] = '~', ch[n * 2 + 1] = '|';
  for (register int i = 1; i <= n; i++) {
    ch[i * 2 - 1] = '|', ch[i * 2] = s[i];
  }
  for (register int i = 1; i <= 2 * n + 1; i++) {
    rad[i] = i < mxr ? min(rad[(mid << 1) - i], rad[mid] + mid - i) : 1;
    while (ch[i + rad[i]] == ch[i - rad[i]]) {
      rad[i]++;
    }
    rad[i] + i > mxr ? mxr = rad[i] + i, mid = i : 1;
  }
  for (register int i = 1; i <= 2 * n + 1; i++) {
    lx = i - rad[i] + 1, rx = i + rad[i] - 1, lx += lx & 1, rx -= rx & 1;
    if (lx <= rx) {
      lx >>= 1, rx >>= 1, f[lx]++, f[(i >> 1) + 1]--, g[(i + 1) >> 1]++,
          g[rx + 1]--;
      c = (c + (i >> 1) - lx + 1) % mod;
    }
  }
  for (register int i = 1; i <= n; i++) {
    f[i] += f[i - 1], g[i] += g[i - 1];
  }
  for (register int i = 1; i <= n; i++) {
    g[i] = (g[i] + g[i - 1]) % mod,
    res = (res + (long long int)f[i] * g[i - 1] % mod) % mod;
  }
  yout << ((long long int)c * (c - 1) % mod * inv2 % mod - res + mod) % mod
       << '\n';
}
