#include <bits/stdc++.h>
using namespace std;
const long long mod = 51123987;
long long ans = 0, tot = 0, S1[2000010], S2[2000010], S3[2000010];
int pal[5000010];
int n, m;
char tmp[2000010], ss[2000010];
void transfer(char *s) {
  ss[0] = '+';
  for (int i = 0; i <= n; i++) ss[i * 2 + 1] = '#', ss[i * 2 + 2] = s[i];
  ss[n * 2 + 2] = '-';
}
void manacher(char *s) {
  int mx = 0, id = 0;
  m = 2 * n + 1;
  for (int i = 1; i <= m; i++) {
    if (mx >= i)
      pal[i] = min(mx - i + 1, pal[id * 2 - i]);
    else
      pal[i] = 1;
    while (s[i + pal[i]] == s[i - pal[i]]) pal[i]++;
    if (i + pal[i] - 1 > mx) mx = i + pal[i] - 1, id = i;
  }
}
int main() {
  scanf("%d", &n);
  scanf("%s", tmp);
  transfer(tmp);
  manacher(ss);
  for (int i = 1; i < m; i++)
    if (i & 1) {
      S1[(i >> 1) + 1]++;
      S1[(i >> 1) + ((pal[i] - 1) >> 1) + 1]--;
    } else {
      S1[(i >> 1)]++;
      S1[(i >> 1) + ((pal[i] - 2) >> 1) + 1]--;
    }
  for (int i = 1; i <= n; i++)
    S1[i] = (S1[i - 1] + S1[i]) % mod, tot = (tot + S1[i]) % mod;
  for (int i = 1; i <= n; i++) S2[i] = (S2[i - 1] + S1[i]) % mod;
  for (int i = 1; i <= n; i++) S3[i] = (S3[i - 1] + S2[i]) % mod;
  for (int i = 1; i < m; i++)
    if (i & 1)
      ans = (ans + S3[(i >> 1) - 1] - S3[(i >> 1) - ((pal[i] - 1) >> 1) - 1] +
             mod) %
            mod;
    else
      ans = (ans + S3[(i >> 1) - 1] - S3[(i >> 1) - ((pal[i] - 2) >> 1) - 2] +
             mod) %
            mod;
  printf("%I64d\n", (tot * (tot - 1) / 2 % mod - ans + mod) % mod);
  return 0;
}
