#include <bits/stdc++.h>
using namespace std;
const int N = 4e6 + 2;
const int P = 51123987;
char a[N + 3];
int p[N + 3];
long long f[N + 3];
long long g[N + 3];
int n;
void manacher() {
  int mxid = 1, mx = 1;
  p[1] = 1;
  for (int i = 2; i <= 2 * n + 1; i++) {
    if (i > mx) {
      p[i] = 1;
    } else {
      p[i] = min(p[2 * mxid - i], mx - i + 1);
    }
    while (i - p[i] > 0 && i + p[i] <= 2 * n + 1 &&
           a[i + p[i]] == a[i - p[i]]) {
      p[i]++;
    }
    if (i + p[i] - 1 > mx) {
      mx = i + p[i] - 1;
      mxid = i;
    }
  }
}
int main() {
  scanf("%d", &n);
  scanf("%s", a + 1);
  for (int i = n; i >= 1; i--) a[2 * i] = a[i];
  for (int i = 1; i <= 2 * n + 1; i += 2) a[i] = '#';
  manacher();
  long long ans0 = 0ll, ans1 = 0ll, ans = 0ll;
  for (int i = 1; i <= 2 * n + 1; i++) {
    g[i - p[i] + 1]++;
    g[i + 1]--;
    f[i]++;
    f[i + p[i]]--;
    ans0 += (p[i] >> 1);
    ans0 %= P;
  }
  for (int i = 1; i <= 2 * n + 2; i++) f[i] += f[i - 1];
  for (int i = 1; i <= 2 * n + 2; i++) g[i] += g[i - 1];
  for (int i = 2; i <= 2 * n; i += 2) {
    f[i] += (long long)f[i - 2];
    f[i] %= P;
  }
  for (int i = 2; i < 2 * n; i += 2) {
    ans1 += f[i] * g[i + 2];
    ans1 %= P;
  }
  ans = ((ans0 * (ans0 - 1ll) / 2ll - ans1) % P + P) % P;
  printf("%I64d\n", ans % P);
  return 0;
}
