#include <bits/stdc++.h>
using namespace std;
priority_queue<int> QwQ;
int n, l;
long long f[4000005], sum[4000005], cnt[4000005];
char s[4000005], s1[4000005];
long long sumr = 0, suml = 0, sumt = 0, ans = 0, Mod = 51123987;
int read() {
  int k = 0, f = 1;
  char ch;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    k = (k << 1) + (k << 3) + ch - '0', ch = getchar();
  return k * f;
}
void manancher() {
  int i, j, k, mx = 0, id;
  for (i = 1; i <= l; i++) {
    if (mx > i)
      f[i] = min((long long)mx - i, f[id * 2 - i]);
    else
      f[i] = 0;
    while (s[i + f[i] + 1] == s[i - f[i] - 1]) f[i]++;
    if (i + f[i] > mx) mx = i + f[i], id = i;
  }
}
void solve() {
  int i, j, k;
  for (i = 1; i <= l; i++) {
    if (s[i] != '*') {
      sum[(i + f[i] - 1) / 2 + 1]--, sum[i / 2]++;
      cnt[(i - f[i]) / 2]++, cnt[i / 2 + 1]--;
    } else if (f[i]) {
      sum[(i + f[i] - 1) / 2 + 1]--, sum[(i + 1) / 2]++;
      cnt[(i - f[i]) / 2]++, cnt[(i - 1) / 2 + 1]--;
    }
  }
  suml = cnt[0];
  for (i = 0; i <= n - 2; i++) {
    sumr = (sumr + sum[i] + Mod) % Mod;
    suml = (suml + cnt[i + 1] + Mod) % Mod;
    sumt = (sumt + sumr + Mod) % Mod;
    ans = (ans + sumt * suml + Mod) % Mod;
  }
  sumr = (sumr + sum[n - 1] + Mod) % Mod, sumt = (sumt + sumr + Mod) % Mod;
  printf("%I64d\n", (sumt * (sumt - 1) / 2 % Mod - ans + Mod) % Mod);
}
void init() {
  int i, j, k;
  n = read();
  scanf("%s", s1);
  l = strlen(s1);
  s[0] = '&';
  for (i = 0; i <= l - 2; i++) {
    s[i << 1 | 1] = s1[i];
    s[(i << 1) + 2] = '*';
  }
  s[(l - 1) << 1 | 1] = s1[l - 1];
  l = (l - 1) << 1 | 1;
  s[l + 1] = '%';
  manancher();
  solve();
}
void work() { int i, j, k; }
int main() {
  init();
  work();
  return 0;
}
