#include <bits/stdc++.h>
using namespace std;
char S[5000005], T[5000005];
int n, l = 1, tot = 0, R[5000005], st[5000005], ed[5000005];
void modify() {
  T[0] = '$', T[1] = '#';
  for (int i = 0; i < n; ++i) T[++l] = S[i], T[++l] = '#';
  T[++l] = '\0';
}
void Manacher() {
  int p = 0, mx = 0;
  for (int i = 1; i < l; ++i) {
    R[i] = (mx > i) ? min(R[2 * p - i], mx - i) : 1;
    while (T[i - R[i]] == T[i + R[i]]) R[i]++;
    if (mx < i + R[i]) mx = i + R[i], p = i;
    st[i - R[i] + 1]++, st[i + 1]--;
    ed[i]++, ed[i + R[i]]--, tot = (tot + R[i] / 2) % 51123987;
  }
  tot = (1ll * tot * (tot - 1) / 2) % 51123987;
}
int main() {
  int i, ans = 0, sum = 0;
  scanf("%d%s", &n, S);
  modify(), Manacher();
  for (i = 1; i < l; i++) {
    st[i] += st[i - 1];
    ed[i] += ed[i - 1];
    if (T[i] != '#') {
      ans = (ans + 1ll * sum * st[i] % 51123987) % 51123987;
      sum = (sum + ed[i]) % 51123987;
    }
  }
  printf("%d", (tot - ans + 51123987) % 51123987);
  return 0;
}
