#include <bits/stdc++.h>
using namespace std;
const int md = 51123987;
int n;
char a[4000010];
int p[4000010];
int s1[2000010], s2[2000010];
int s;
int ans;
inline void add(int &x, int y) {
  x += y;
  if (x >= md) x -= md;
}
inline void read(char &x) {
  x = getchar();
  while (x < 'a' || x > 'z') x = getchar();
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    read(a[i + i]);
    a[i + i - 1] = '.';
  }
  a[n + n + 1] = '.';
  int m = 0, r = 0;
  for (int i = 1; i <= n + n + 1; i++) {
    if (r >= i) p[i] = min(r - i, p[m + m - i]);
    while (i > p[i] + 1 && i + p[i] + 1 <= n + n + 1 &&
           a[i - p[i] - 1] == a[i + p[i] + 1])
      p[i]++;
    if (i + p[i] > r) m = i, r = i + p[i];
    int t = (p[i] + 1) / 2;
    if (i & 1) {
      if (!p[i]) continue;
      s1[i / 2 + 1]++;
      s1[(i + p[i]) / 2 + 1]--;
      s2[(i - p[i]) / 2 + 1]++;
      s2[i / 2 + 1]--;
    } else {
      s1[i / 2]++;
      s1[(i + p[i]) / 2 + 1]--;
      s2[(i - p[i]) / 2 + 1]++;
      s2[i / 2 + 1]--;
    }
    add(s, t);
    add(ans, md - 1LL * s * t % md);
    add(ans, (1LL * t * (t - 1) / 2LL) % md);
  }
  for (int i = 1; i <= n; i++) add(s1[i], s1[i - 1]), add(s2[i], s2[i - 1]);
  s = 0;
  for (int i = 1; i <= n; i++) {
    add(s, s2[i]);
    add(ans, 1LL * s * s1[i] % md);
  }
  printf("%d", ans);
  return 0;
}
