#include <bits/stdc++.h>
using namespace std;
const int N = 2000010;
int rad[N << 1];
char s[N], t[N << 1];
void manacher(char *s) {
  int n = strlen(s), len = 0;
  t[len++] = '^';
  t[len++] = '#';
  for (int i = 0; i < n; ++i) {
    t[len++] = s[i];
    t[len++] = '#';
  }
  t[len] = 0;
  int i = 1, j = 1, k;
  while (i < len) {
    while (t[i - j] == t[i + j]) ++j;
    rad[i] = j;
    for (k = 1; k < j && rad[i - k] != rad[i] - k; ++k) {
      rad[i + k] = min(rad[i - k], rad[i] - k);
    }
    i += k;
    j = max(j - k, 1);
  }
}
int st[N << 1], ed[N << 1];
int a[N << 1], b[N << 1];
int n;
int sumed[N];
long long ans;
const int P = 51123987;
int main() {
  scanf("%d", &n);
  scanf("%s", s);
  manacher(s);
  n = 2 * n + 1;
  for (int i = 1; i <= n; i++) {
    a[i - rad[i] + 1]++;
    a[i + 1]--;
    b[i]++;
    b[i + rad[i]]--;
  }
  for (int i = 1; i <= n; i++)
    st[i] = st[i - 1] + a[i], ed[i] = ed[i - 1] + b[i];
  n /= 2;
  for (int i = 1; i <= n; i++) st[i] = st[i * 2], ed[i] = ed[i * 2];
  for (int i = 1; i <= n; i++) sumed[i] = (sumed[i - 1] + ed[i]) % P;
  ans = ((long long)sumed[n] * (sumed[n] - 1) >> 1) % P;
  for (int i = 1; i <= n; i++)
    ans = (ans - (long long)sumed[i - 1] * st[i]) % P;
  cout << (ans + P) % P << endl;
  return 0;
}
