#include <bits/stdc++.h>
using namespace std;
const int N = 4001000, op = 51123987;
int n, m, ans = 0;
char s[N];
int a[N], q[N >> 1], h[N >> 1];
void init() {
  scanf("%d%s", &n, s + 1);
  for (int i = n; i > 0; --i) s[i * 2 + 1] = '#', s[i * 2] = s[i];
  s[1] = '#';
  m = n * 2 + 1;
  s[0] = '?', s[m + 1] = '!';
  for (int i = 1, j = 1, k = 0; i <= m; ++i) {
    a[i] = (k >= i ? min(a[j * 2 - i], k - i) : 0);
    while (s[i - a[i] - 1] == s[i + a[i] + 1]) ++a[i];
    if (i + a[i] > k) k = i + a[j = i];
  }
}
void chn(int *t, const int x, const int y) {
  for (int i = x; i <= n; i += i & -i) t[i] += y;
}
int ask(int *t, const int x) {
  int p = 0;
  for (int i = x; i > 0; i -= i & -i) p += t[i];
  return p;
}
void Gans() {
  for (int i = 1; i <= m; ++i)
    if (s[i] != '#' || a[i] != 0) {
      int x = (i - a[i] + 1) / 2, y = (i + a[i] - 1) / 2;
      if (s[i] != '#') {
        chn(q, n - i / 2 + 1, 1), chn(q, n - x + 2, -1);
        chn(h, i / 2, 1), chn(h, y + 1, -1);
      } else {
        chn(q, n - (i - 1) / 2 + 1, 1), chn(q, n - x + 2, -1);
        chn(h, (i + 1) / 2, 1), chn(h, y + 1, -1);
      }
    }
  for (int i = 1, now = 0, j; i <= n; ++i) {
    j = ask(q, n - i + 1);
    ans = ((long long)j * now + (long long)j * (j - 1) / 2 + ans) % op;
    now += j - ask(h, i);
    while (now >= op) now -= op;
    while (now < op) now += op;
  }
  while (ans < 0) ans += op;
  printf("%d\n", ans);
}
int main() {
  init();
  Gans();
  return 0;
}
