#include <bits/stdc++.h>
using namespace std;
char s[6000000];
int n;
int d1[6000000], d2[6000000];
void imp() {
  int l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k = (i > r ? 0 : min(d1[l + r - i], r - i)) + 1;
    while (i + k < n && i - k >= 0 && s[i + k] == s[i - k]) ++k;
    d1[i] = --k;
    if (i + k > r) l = i - k, r = i + k;
  }
}
void par() {
  int l = 0, r = -1;
  for (int i = 0; i < n; ++i) {
    int k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1)) + 1;
    while (i + k - 1 < n && i - k >= 0 && s[i + k - 1] == s[i - k]) ++k;
    d2[i] = --k;
    if (i + k - 1 > r) l = i - k, r = i + k - 1;
  }
}
int ini[6000000 + 10], fim[6000000 + 10];
void updateini(int idx, int v) {
  idx++;
  for (int x = idx; x < 6000000; x += (x & -x)) {
    ini[x] += v;
  }
}
int getini(int idx) {
  idx++;
  int s = 0;
  for (int x = idx; x > 0; x -= (x & -x)) {
    s += ini[x];
  }
  return s;
}
void updatefim(int idx, int v) {
  idx++;
  for (int x = idx; x < 6000000; x += (x & -x)) {
    fim[x] += v;
  }
}
int getfim(int idx) {
  idx++;
  int s = 0;
  for (int x = idx; x > 0; x -= (x & -x)) {
    s += fim[x];
  }
  return s;
}
int main() {
  scanf("%d%s", &n, s);
  imp();
  par();
  memset(ini, 0, sizeof ini);
  for (int i = 0; i < n; i++) {
    int c = i - d1[i], fi = i + d1[i];
    updateini(c, 1);
    updateini(i + 1, -1);
    updatefim(i, 1);
    updatefim(fi + 1, -1);
  }
  for (int i = 0; i < n; i++) {
    if (!d2[i]) continue;
    int c = i - d2[i], fi = i + d2[i] - 1;
    updateini(c, 1);
    updateini(i, -1);
    updatefim(i, 1);
    updatefim(fi + 1, -1);
  }
  long long ans = 0;
  long long acc = 0;
  for (int i = 0; i < n; i++) {
    long long g = (long long)getini(i);
    ans += acc * g;
    ans %= 51123987;
    ans += ((g) * (g - 1)) / 2LL;
    ans %= 51123987;
    acc += g;
    acc -= getfim(i);
  }
  cout << ans << endl;
  return 0;
}
